On plane subgraphs of complete topological drawings

Alfredo García Olaverri, Javier Tejel Altarriba, Alexander Pilz


Topological drawings are representations of graphs in the plane, where vertices are represented by points, and edges by simple curves connecting the points. A drawing is simple if two edges intersect at most in a single point, either at a common endpoint or at a proper crossing. In this paper we study properties of maximal plane subgraphs of simple drawings Dn of the complete graph Kn on n vertices. Our main structural result is that maximal plane subgraphs are 2-connected and what we call essentially 3-edge-connected. Besides, any maximal plane subgraph contains at least ⌈3n/2⌉ edges. We also address the problem of obtaining a plane subgraph of Dn with the maximum number of edges, proving that this problem is NP-complete. However, given a plane spanning connected subgraph of Dn, a maximum plane augmentation of this subgraph can be found in O(n3) time. As a side result, we also show that the problem of finding a largest compatible plane straight-line graph of two labeled point sets is NP-complete.


Graph, topological drawing, plane subgraph, NP-complete problem

Full Text:


DOI: https://doi.org/10.26493/1855-3974.2226.e93

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications