TY - GEN
T1 - Balanced Schnyder Woods for Planar Triangulations
T2 - 27th International Symposium on Graph Drawing and Network Visualization, GD 2019
AU - Castelli Aleardi, Luca
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.
PY - 2019/1/1
Y1 - 2019/1/1
N2 - In this work we consider balanced Schnyder woods for planar graphs, which are Schnyder woods where the number of incoming edges of each color at each vertex is balanced as much as possible. We provide a simple linear-time heuristic leading to obtain well balanced Schnyder woods in practice. As test applications we consider two important algorithmic problems: the computation of Schnyder drawings and of small cycle separators. While not being able to provide theoretical guarantees, our experimental results (on a wide collection of planar graphs) suggest that the use of balanced Schnyder woods leads to an improvement of the quality of the layout of Schnyder drawings, and provides an efficient tool for computing short and balanced cycle separators.
AB - In this work we consider balanced Schnyder woods for planar graphs, which are Schnyder woods where the number of incoming edges of each color at each vertex is balanced as much as possible. We provide a simple linear-time heuristic leading to obtain well balanced Schnyder woods in practice. As test applications we consider two important algorithmic problems: the computation of Schnyder drawings and of small cycle separators. While not being able to provide theoretical guarantees, our experimental results (on a wide collection of planar graphs) suggest that the use of balanced Schnyder woods leads to an improvement of the quality of the layout of Schnyder drawings, and provides an efficient tool for computing short and balanced cycle separators.
U2 - 10.1007/978-3-030-35802-0_9
DO - 10.1007/978-3-030-35802-0_9
M3 - Conference contribution
AN - SCOPUS:85076889530
SN - 9783030358013
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 114
EP - 121
BT - Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Proceedings
A2 - Archambault, Daniel
A2 - Tóth, Csaba D.
PB - Springer
Y2 - 17 September 2019 through 20 September 2019
ER -