Compatible Spanning Trees in Simple Drawings of Kn

Oswin Aichholzer, Kristin Knorr, Wolfgang Mulzer, Nicolas El Maalouly, Johannes Obenaus, Rosna Paul*, Meghana M. Reddy, Birgit Vogtenhuber, Alexandra Weinberger

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


For a simple drawing D of the complete graph Kn, two (plane) subdrawings are compatible if their union is plane. Let TD be the set of all plane spanning trees on D and F(TD) be the compatibility graph that has a vertex for each element in TD and two vertices are adjacent if and only if the corresponding trees are compatible. We show, on the one hand, that F(TD) is connected if D is a cylindrical, monotone, or strongly c-monotone drawing. On the other hand, we show that the subgraph of F(TD) induced by stars, double stars, and twin stars is also connected. In all cases the diameter of the corresponding compatibility graph is at most linear in n.

Original languageEnglish
Title of host publicationGraph Drawing and Network Visualization - 30th International Symposium, GD 2022, Tokyo, Japan, September 13-16, 2022, Revised Selected Papers
EditorsPatrizio Angelini, Reinhard von Hanxleden
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages9
ISBN (Electronic)978-303122202-3
ISBN (Print)9783031222023
Publication statusPublished - 2023
Event30th International Symposium on Graph Drawing and Network Visualization: GD 2022 - Tokyo, Japan
Duration: 13 Sept 202216 Jan 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13764 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference30th International Symposium on Graph Drawing and Network Visualization
Abbreviated titleGD 2022


  • Compatibility graph
  • Plane spanning tree
  • Simple drawing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fields of Expertise

  • Information, Communication & Computing


Dive into the research topics of 'Compatible Spanning Trees in Simple Drawings of Kn'. Together they form a unique fingerprint.

Cite this