TY - GEN
T1 - Low ply graph drawing
AU - Di Giacomo, Emilio
AU - Didimo, Walter
AU - Hong, Seok Hee
AU - Kaufmann, Michael
AU - Kobourov, Stephen G.
AU - Liotta, Giuseppe
AU - Misue, Kazuo
AU - Symvonis, Antonios
AU - Yen, Hsu Chun
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2016/1/20
Y1 - 2016/1/20
N2 - We consider the problem of characterizing graphs with low ply number and algorithms for creating layouts of graphs with low ply number. Informally, the ply number of a straight-line drawing of a graph is defined as the maximum number of overlapping disks, where each disk is associated with a vertex and has a radius that is half the length of the longest edge incident to that vertex. We show that internally triangulated biconnected planar graphs that admit a drawing with ply number 1 can be recognized in O(n log n) time, while the problem is in general NP-hard. We also show several classes of graphs that have 1-ply drawings. We then show that binary trees, stars, and caterpillars have 2-ply drawings, while general trees have (h+1)-ply drawings, where h is the height of the tree. Finally we discuss some generalizations of the notion of a ply number.
AB - We consider the problem of characterizing graphs with low ply number and algorithms for creating layouts of graphs with low ply number. Informally, the ply number of a straight-line drawing of a graph is defined as the maximum number of overlapping disks, where each disk is associated with a vertex and has a radius that is half the length of the longest edge incident to that vertex. We show that internally triangulated biconnected planar graphs that admit a drawing with ply number 1 can be recognized in O(n log n) time, while the problem is in general NP-hard. We also show several classes of graphs that have 1-ply drawings. We then show that binary trees, stars, and caterpillars have 2-ply drawings, while general trees have (h+1)-ply drawings, where h is the height of the tree. Finally we discuss some generalizations of the notion of a ply number.
UR - https://www.scopus.com/pages/publications/84963787567
UR - https://www.scopus.com/pages/publications/84963787567#tab=citedBy
U2 - 10.1109/IISA.2015.7388020
DO - 10.1109/IISA.2015.7388020
M3 - Conference contribution
AN - SCOPUS:84963787567
T3 - IISA 2015 - 6th International Conference on Information, Intelligence, Systems and Applications
BT - IISA 2015 - 6th International Conference on Information, Intelligence, Systems and Applications
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 6th International Conference on Information, Intelligence, Systems and Applications, IISA 2015
Y2 - 6 July 2015 through 8 July 2015
ER -