Efficient barycenter algorithm for drawing hierarchical graphs with minimum edge crossings

Alaa A. K. Ismaeel; Pradyumn Kumar Shukla; Hartmut Schmeck

doi:10.1117/12.913044

30 September 2011 Efficient barycenter algorithm for drawing hierarchical graphs with minimum edge crossings

Alaa A. K. Ismaeel, Pradyumn Kumar Shukla, Hartmut Schmeck

Proceedings Volume 8285, International Conference on Graphic and Image Processing (ICGIP 2011); 82850A (2011) https://doi.org/10.1117/12.913044
Event: 2011 International Conference on Graphic and Image Processing, 2011, Cairo, Egypt

Abstract

Graph Drawing is a branch of computer graphics that addresses the problem of constructing geometric representations of conceptual structures that are modeled by graphs. Crossing reduction is one of the crucial problems in drawing networks that are presented in a hierarchical manner which is solved by repeated layer-by-layer techniques or by global ones. In this paper, we introduce a new efficient algorithm for drawing hierarchical graphs based on the well-known barycenter algorithm. Our algorithm improves the existing layer-by-layer techniques by 15-25% and recent global algorithms by 5% further reduction in the number of crossings.

Citation Download Citation

Alaa A. K. Ismaeel, Pradyumn Kumar Shukla, and Hartmut Schmeck "Efficient barycenter algorithm for drawing hierarchical graphs with minimum edge crossings", Proc. SPIE 8285, International Conference on Graphic and Image Processing (ICGIP 2011), 82850A (30 September 2011); https://doi.org/10.1117/12.913044

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available