Bipartite and Series-Parallel Graphs Without Planar Lombardi Drawings

Autor:	Eppstein, David
Rok vydání:	2019
Předmět:	Computer Science - Computational Geometry
Zdroj:	J. Graph Algorithms & Applications 25 (1): 549-562, 2021
Druh dokumentu:	Working Paper
DOI:	10.7155/jgaa.00571
Popis:	We find a family of planar bipartite graphs all of whose Lombardi drawings (drawings with circular arcs for edges, meeting at equal angles at the vertices) are nonplanar. We also find families of embedded series-parallel graphs and apex-trees (graphs formed by adding one vertex to a tree) for which there is no planar Lombardi drawing consistent with the given embedding. Comment: 10 pages, 6 figures. A preliminary version of this paper appeared at the 31st Canadian Conference in Computational Geometry
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1906.04401 Zobrazit plný text záznamu View this record from Arxiv