Earlier Version
Clustered planarity testing revisited
Fulek R, Kynčl J, Malinović I, Pálvölgyi D. 2014. Clustered planarity testing revisited. International Symposium on Graph Drawing. , LNCS, vol. 8871, 428–436.
Download
No fulltext has been uploaded. References only!
[Preprint]
Conference Paper
| Published
| English
Scopus indexed
Author
Fulek, RadoslavISTA 
;
Kynčl, Jan;
Malinović, Igor;
Pálvölgyi, Dömötör
;
Kynčl, Jan;
Malinović, Igor;
Pálvölgyi, DömötörDepartment
Series Title
LNCS
Abstract
The Hanani–Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this classical result to clustered graphs with two disjoint clusters, and show that a straightforward extension of our result to flat clustered graphs with three or more disjoint clusters is not possible.
We also give a new and short proof for a related result by Di Battista and Frati based on the matroid intersection algorithm.
Publishing Year
Date Published
2014-01-01
Proceedings Title
International Symposium on Graph Drawing
Volume
8871
Page
428-436
ISSN
IST-REx-ID
Cite this
Fulek R, Kynčl J, Malinović I, Pálvölgyi D. Clustered planarity testing revisited. In: International Symposium on Graph Drawing. Vol 8871. Cham: Springer Nature; 2014:428-436. doi:10.1007/978-3-662-45803-7_36
Fulek, R., Kynčl, J., Malinović, I., & Pálvölgyi, D. (2014). Clustered planarity testing revisited. In International Symposium on Graph Drawing (Vol. 8871, pp. 428–436). Cham: Springer Nature. https://doi.org/10.1007/978-3-662-45803-7_36
Fulek, Radoslav, Jan Kynčl, Igor Malinović, and Dömötör Pálvölgyi. “Clustered Planarity Testing Revisited.” In International Symposium on Graph Drawing, 8871:428–36. Cham: Springer Nature, 2014. https://doi.org/10.1007/978-3-662-45803-7_36.
R. Fulek, J. Kynčl, I. Malinović, and D. Pálvölgyi, “Clustered planarity testing revisited,” in International Symposium on Graph Drawing, 2014, vol. 8871, pp. 428–436.
Fulek R, Kynčl J, Malinović I, Pálvölgyi D. 2014. Clustered planarity testing revisited. International Symposium on Graph Drawing. , LNCS, vol. 8871, 428–436.
Fulek, Radoslav, et al. “Clustered Planarity Testing Revisited.” International Symposium on Graph Drawing, vol. 8871, Springer Nature, 2014, pp. 428–36, doi:10.1007/978-3-662-45803-7_36.
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1305.4519
Google Scholar