Geometric simultaneous embeddings of a graph and a matching

S. Cabello, M.J. Kreveld, van, G. Liotta, H. Meijer, B. Speckmann, K.A.B. Verbeek

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

2 Citations (Scopus)


The geometric simultaneous embedding problem asks whether two planar graphs on the same set of vertices in the plane can be drawn using straight lines, such that each graph is plane. Geometric simultaneous embedding is a current topic in graph drawing and positive and negative results are known for various classes of graphs. So far only connected graphs have been considered. In this paper we present the first results for the setting where one of the graphs is a matching. In particular, we show that there exists a planar graph and a matching which do not admit a geometric simultaneous embedding. This generalizes the same result for a planar graph and a path. On the positive side, we describe algorithms that compute a geometric simultaneous embedding of a matching and a wheel, outerpath, or tree. Our proof for a matching and a tree sheds new light on a major open question: do a tree and a path always admit a geometric simultaneous embedding? Our drawing algorithms minimize the number of orientations used to draw the edges of the matching. Specifically, when embedding a matching and a tree, we can draw all matching edges horizontally. When embedding a matching and a wheel or an outerpath, we use only two orientations.
Original languageEnglish
Title of host publicationGraph Drawing (17th International Symposium, GD'09, Chicago, IL, USA, September 22-25, 2009. Revised Papers)
EditorsD. Eppstein, E.R. Gansner
Place of PublicationBerlin
ISBN (Print)978-3-642-11804-3
Publication statusPublished - 2010

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Geometric simultaneous embeddings of a graph and a matching'. Together they form a unique fingerprint.

Cite this