Earlier Version

Hanani-Tutte for radial planarity

Fulek R, Pelsmajer M, Schaefer M. 2015. Hanani-Tutte for radial planarity. GD: Graph Drawing and Network Visualization, LNCS, vol. 9411, 99–110.

Download
OA IST-2016-594-v1+1_HTCylinder_GD_Revision.pdf 330.13 KB [Submitted Version]

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. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Tóth.
Publishing Year
Date Published
2015-11-27
Publisher
Springer
Acknowledgement
The research leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement no [291734].
Volume
9411
Page
99 - 110
Conference
GD: Graph Drawing and Network Visualization
Conference Location
Los Angeles, CA, USA
Conference Date
2015-09-24 – 2015-09-26
IST-REx-ID

Cite this

Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity. In: Vol 9411. Springer; 2015:99-110. doi:10.1007/978-3-319-27261-0_9
Fulek, R., Pelsmajer, M., & Schaefer, M. (2015). Hanani-Tutte for radial planarity (Vol. 9411, pp. 99–110). Presented at the GD: Graph Drawing and Network Visualization, Los Angeles, CA, USA: Springer. https://doi.org/10.1007/978-3-319-27261-0_9
Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte for Radial Planarity,” 9411:99–110. Springer, 2015. https://doi.org/10.1007/978-3-319-27261-0_9.
R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity,” presented at the GD: Graph Drawing and Network Visualization, Los Angeles, CA, USA, 2015, vol. 9411, pp. 99–110.
Fulek R, Pelsmajer M, Schaefer M. 2015. Hanani-Tutte for radial planarity. GD: Graph Drawing and Network Visualization, LNCS, vol. 9411, 99–110.
Fulek, Radoslav, et al. Hanani-Tutte for Radial Planarity. Vol. 9411, Springer, 2015, pp. 99–110, doi:10.1007/978-3-319-27261-0_9.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
685f91bd077a951ba067d42cce75409e


Material in ISTA:
Later Version
Later Version

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar