Drawing partially embedded and simultaneously planar graphs

Timothy M. Chan, Fabrizio Frati, Carsten Gutwenger, Anna Lubiw, Petra Mutzel, Marcus Schaefer

Research output: Contribution to journalArticlepeer-review

Abstract

We investigate the problem of constructing planar drawings with few bends for two related problems, the partially embedded graph (PEG) problem—to extend a straight-line planar drawing of a subgraph to a planar drawing of the whole graph—and the simultaneous planarity (SEFE) problem—to find planar drawings of two graphs that coincide on shared vertices and edges. In both cases we show that if the required planar drawings exist, then there are planar drawings with a linear number of bends per edge and, in the case of simultaneous planarity, a constant number of crossings between every pair of edges. Our proofs provide efficient algorithms if the combinatorial embedding information about the drawing is given. Our result on partially embedded graph drawing generalizes a classic result of Pach andWenger showing that any planar graph can be drawn with fixed locations for its vertices and with a linear number of bends per edge.

Original languageEnglish (US)
Pages (from-to)25-39
Number of pages15
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8871
DOIs
StatePublished - 2014
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Drawing partially embedded and simultaneously planar graphs'. Together they form a unique fingerprint.

Cite this