Minimum length embedding of planar graphs at fixed vertex locations

Timothy M. Chan, Hella Franziska Hoffmann, Stephen Kiazyk, Anna Lubiw

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the problem of finding a planar embedding of a graph at fixed vertex locations that minimizes the total edge length. The problem is known to be NP-hard. We give polynomial time algorithms achieving an O(√n log n) approximation for paths and matchings, and an O(n) approximation for general graphs.

Original languageEnglish (US)
Title of host publicationGraph Drawing - 21st International Symposium, GD 2013, Revised Selected Papers
PublisherSpringer-Verlag Berlin Heidelberg
Pages376-387
Number of pages12
ISBN (Print)9783319038407
DOIs
StatePublished - 2013
Externally publishedYes
Event21st International Symposium on Graph Drawing, GD 2013 - Bordeaux, France
Duration: Sep 23 2013Sep 25 2013

Publication series

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

Other

Other21st International Symposium on Graph Drawing, GD 2013
CountryFrance
CityBordeaux
Period9/23/139/25/13

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Minimum length embedding of planar graphs at fixed vertex locations'. Together they form a unique fingerprint.

Cite this