Abstract
We define some Schnyder-type combinatorial structures on a class of planar triangulations of the pentagon which are closely related to 5-connected triangulations. The combinatorial structures have three incarnations defined in terms of orientations, corner-labelings, and woods respectively. The wood incarnation consists in 5 spanning trees crossing each other in an orderly fashion. Similarly as for Schnyder woods on triangulations, it induces, for each vertex, a partition of the inner triangles into face-connected regions (5 regions here). We show that the induced barycentric vertex-placement, where each vertex is at the barycenter of the 5 outer vertices with weights given by the number of faces in each region, yields a planar straight-line drawing.
OB was partially supported by NSF Grant DMS-2154242. EF was partially supported by the project ANR19-CE48-011-01 (COMBINÉ), and the project ANR-20-CE48-0018 (3DMaps).
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
Notes
- 1.
If we use an affine transformation to have \(v_1\), \(v_2\) and \(v_5\) placed at (0, 0), (0, 1) and (1, 0) respectively, then we get a drawing with vertex-coordinates in \(\mathbb {Q}(\sqrt{5})\).
References
Bernardi, O., Fusy, É.: Schnyder decompositions for regular plane graphs and application to drawing. Algorithmica 62(3), 1159–1197 (2012)
Bernardi, O., Fusy, É.: Unified bijections for maps with prescribed degrees and girth. J. Comb. Theory, Ser. A 119, 1351–1387 (2012)
Bernardi, O., Fusy, É., Liang, S.: Grand Schnyder woods. arXiv preprint: arXiv:2303.15630 (2023)
Bernardi, O., Fusy, É., Liang, S.: A Schnyder-type drawing algorithm for 5-connected triangulations. arXiv preprint: arXiv:2305.19058v2 (2023)
Biedl, T., Kant, G.: A better heuristic for orthogonal graph drawings. Comput. Geom. Theory Appl 9, 159–180 (1998)
Bonichon, N.: A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths. Discrete Math. 298, 104–114 (2005)
Bonichon, N., Felsner, S., Mosbah, M.: Convex drawings of 3-connected plane graphs. Algorithmica 47(4), 399–420 (2007)
Chrobak, M., Kant, G.: Convex grid drawings of 3-connected planar graphs. Int. J. Comput. Geometry Appl. 7(03), 211–223 (1997)
Colin de Verdière, E.: Shortening of curves and decomposition of surfaces. Ph.D. thesis, Université Paris 7 (2003)
Di Battista, G., Tamassia, R., Vismara, L.: Output-sensitive reporting of disjoint paths. Algorithmica 23(4), 302–340 (1999)
Felsner, S.: Convex drawings of planar graphs and the order dimension of 3-polytopes. Order 18, 19–37 (2001)
Felsner, S.: Geodesic embeddings and planar graphs. Order 20, 135–150 (2003)
Felsner, S., Schrezenmaier, H., Steiner, R.: Pentagon contact representations. Electr. J. Comb. 25(3), P3.39 (2018)
Felsner, S., Zickfeld, F.: Schnyder woods and orthogonal surfaces. Discrete Comput. Geometry 40(1), 103–126 (2008)
de Fraysseix, H., Pach, J., Pollack, R.: Small sets supporting Fáry embeddings of planar graphs. In: Proceedings of STOC, pp. 426–433. ACM (1988)
Fusy, É.: Transversal structures on triangulations: a combinatorial study and straight-line drawings. Discrete Math. 309, 1870–1894 (2009)
Gao, Z., Wanless, I., Wormald, N.: Counting 5-connected planar triangulations. J. Graph Theory 38(1), 18–35 (2001)
He, X.: On finding the rectangular duals of planar triangulated graphs. SIAM J. Comput. 22, 1218–1226 (1993)
He, X.: Grid embedding of 4-connected plane graphs. Discrete Comput. Geometry 17(3), 339–358 (1997)
Miller, E.: Planar graphs as minimal resolutions of trivariate monomial ideals. Doc. Math. 7, 43–90 (2002)
Miura, K.: Grid drawings of five-connected plane graphs. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 105(9), 1228–1234 (2022)
Miura, K., Nakano, S., Nishizeki, T.: Grid drawings of 4-connected plane graphs. Discret. Comput. Geom. 26(1), 73–87 (2001)
Nagai, S., Nakano, S.: A linear-time algorithm to find independent spanning trees in maximal planar graphs. In: Graph-Theoretic Concepts in Computer Science: WG’2000, pp. 290–301 (2000)
Schnyder, W.: Planar graphs and poset dimension. Order 5(4), 323–343 (1989)
Schnyder, W.: Embedding planar graphs in the grid. In: Symposium on Discrete Algorithms (SODA), pp. 138–148 (1990)
Tamassia, R.: On embedding a graph in a grid with the minimum number of bends. SIAM J. Comput. 16, 421–444 (1987)
Tutte, W.: How to draw a graph. Proc. Lond. Math. Soc. 3(1), 743–767 (1963)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Bernardi, O., Fusy, É., Liang, S. (2023). A Schnyder-Type Drawing Algorithm for 5-Connected Triangulations. In: Bekos, M.A., Chimani, M. (eds) Graph Drawing and Network Visualization. GD 2023. Lecture Notes in Computer Science, vol 14466. Springer, Cham. https://doi.org/10.1007/978-3-031-49275-4_8
Download citation
DOI: https://doi.org/10.1007/978-3-031-49275-4_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-49274-7
Online ISBN: 978-3-031-49275-4
eBook Packages: Computer ScienceComputer Science (R0)