Earlier Version
Hanani-Tutte for radial planarity II
Fulek R, Pelsmajer M, Schaefer M. 2016. Hanani-Tutte for radial planarity II. GD: Graph Drawing and Network Visualization, LNCS, vol. 9801, 468–481.
Download (ext.)
https://arxiv.org/abs/1608.08662
[Preprint]
Conference Paper
| Published
| English
Scopus indexed
Author
Fulek, RadoslavISTA ;
Pelsmajer, Michael;
Schaefer, Marcus
Department
Series Title
LNCS
Abstract
A drawing of a graph G is radial if the vertices of G are placed on concentric circles C1, … , Ck with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. A pair of edges e and f in a graph is independent if e and f do not share a vertex. We show that a graph G is radial planar if G has a radial drawing in which every two independent edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the strong Hanani-Tutte theorem for radial planarity. This characterization yields a very simple algorithm for radial planarity testing.
Publishing Year
Date Published
2016-12-08
Volume
9801
Page
468 - 481
Conference
GD: Graph Drawing and Network Visualization
Conference Location
Athens, Greece
Conference Date
2016-09-19 – 2016-09-21
IST-REx-ID
Cite this
Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity II. In: Vol 9801. Springer; 2016:468-481. doi:10.1007/978-3-319-50106-2_36
Fulek, R., Pelsmajer, M., & Schaefer, M. (2016). Hanani-Tutte for radial planarity II (Vol. 9801, pp. 468–481). Presented at the GD: Graph Drawing and Network Visualization, Athens, Greece: Springer. https://doi.org/10.1007/978-3-319-50106-2_36
Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte for Radial Planarity II,” 9801:468–81. Springer, 2016. https://doi.org/10.1007/978-3-319-50106-2_36.
R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity II,” presented at the GD: Graph Drawing and Network Visualization, Athens, Greece, 2016, vol. 9801, pp. 468–481.
Fulek R, Pelsmajer M, Schaefer M. 2016. Hanani-Tutte for radial planarity II. GD: Graph Drawing and Network Visualization, LNCS, vol. 9801, 468–481.
Fulek, Radoslav, et al. Hanani-Tutte for Radial Planarity II. Vol. 9801, Springer, 2016, pp. 468–81, doi:10.1007/978-3-319-50106-2_36.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Material in ISTA:
Later Version
Earlier Version
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1608.08662