Abstract
We study planar straight-line drawings of graphs that minimize the ratio between the length of the longest and the shortest edge. We answer a question of Lazard et al. [Theor. Comput. Sci. 770 (2019), 88–94] and, for any given constant r, we provide a 2-tree which does not admit a planar straight-line drawing with a ratio bounded by r. When the ratio is restricted to adjacent edges only, we prove that any 2-tree admits a planar straight-line drawing whose edge-length ratio is at most \(4 + \varepsilon \) for any arbitrarily small \(\varepsilon > 0\), hence the upper bound on the local edge-length ratio of partial 2-trees is 4.
The research was initiated during workshop Homonolo 2018. Research partially supported by MIUR, the Italian Ministry of Education, University and Research, under Grant 20174LF3T8 AHeAD: efficient Algorithms for HArnessing networked Data. V. Blažej acknowledges the support of the OP VVV MEYS funded project CZ.02.1.01/0.0/0.0/16_019/0000765 “Research Center for Informatics”. This work was supported by the Grant Agency of the Czech Technical University in Prague, grant No. SGS20/208/OHK3/3T/18. The work of J. Fiala was supported by the grant 19-17314J of the GA ČR.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bhatt, S.N., Cosmadakis, S.S.: The complexity of minimizing wire lengths in VLSI layouts. Inf. Process. Lett. 25(4), 263–267 (1987). https://doi.org/10.1016/0020-0190(87)90173-6
Blažej, V., Fiala, J., Liotta, G.: On the edge-length ratio of 2-trees. CoRR abs/1909.11152 (2019). http://arxiv.org/abs/1909.11152
Borrazzo, M., Frati, F.: On the planar edge-length ratio of planar graphs. JoCG 11(1), 137–155 (2020). https://journals.carleton.ca/jocg/index.php/jocg/article/view/470
Cabello, S., Demaine, E.D., Rote, G.: Planar embeddings of graphs with specified edge lengths. J. Graph Algorithms Appl. 11(1), 259–276 (2007). https://doi.org/10.7155/jgaa.00145
Chen, J., Jiang, A., Kanj, I.A., Xia, G., Zhang, F.: Separability and topology control of quasi unit disk graphs. Wirel. Netw. 17(1), 53–67 (2011). https://doi.org/10.1007/s11276-010-0264-0
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Upper Saddle River (1999)
Eades, P., Wormald, N.C.: Fixed edge-length graph drawing is NP-hard. Discrete Appl. Math. 28(2), 111–134 (1990). https://doi.org/10.1016/0166-218X(90)90110-X
Giacomo, E.D., Liotta, G., Tamassia, R.: Graph drawing. In: Goodman, J.E., O’Rourke, J., Tóth, C.D. (eds.) Handbook of Discrete and Computational Geometry, pp. 247–284. CRC Press LLC, Boca Raton (2017)
Hoffmann, M., van Kreveld, M.J., Kusters, V., Rote, G.: Quality ratios of measures for graph drawing styles. In: Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG 2014, Halifax, Nova Scotia, Canada, 2014. Carleton University, Ottawa, Canada (2014). http://www.cccg.ca/proceedings/2014/papers/paper05.pdf
Lazard, S., Lenhart, W.J., Liotta, G.: On the edge-length ratio of outerplanar graphs. Theor. Comput. Sci. 770, 88–94 (2019). https://doi.org/10.1016/j.tcs.2018.10.002
Nishizeki, T., Rahman, M.S.: Planar graph drawing. In: Lecture Notes Series on Computing, vol. 12. World Scientific (2004). https://doi.org/10.1142/5648
Tamassia, R. (ed.): Handbook on Graph Drawing and Visualization. Chapman and Hall/CRC, Boca Raton (2013). https://www.crcpress.com/Handbook-of-Graph-Drawing-and-Visualization/Tamassia/9781584884125
Acknowledgement
We thank all three reviewers for their positive comments and careful review, which helped improve our contribution.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Blažej, V., Fiala, J., Liotta, G. (2020). On the Edge-Length Ratio of 2-Trees. In: Auber, D., Valtr, P. (eds) Graph Drawing and Network Visualization. GD 2020. Lecture Notes in Computer Science(), vol 12590. Springer, Cham. https://doi.org/10.1007/978-3-030-68766-3_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-68766-3_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-68765-6
Online ISBN: 978-3-030-68766-3
eBook Packages: Computer ScienceComputer Science (R0)