On plane subgraphs of complete topological drawings

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

Research output: Contribution to journalArticlepeer-review


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 Dnof the complete graph Knon 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 Dnwith 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.

Original languageEnglish
Pages (from-to)69-87
Number of pages19
JournalArs Mathematica Contemporanea
Issue number1
Publication statusPublished - 2021


  • Graph
  • NP-complete problem
  • Plane subgraph
  • Topological drawing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Algebra and Number Theory
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On plane subgraphs of complete topological drawings'. Together they form a unique fingerprint.

Cite this