Minimum length embedding of planar graphs at fixed vertex locations

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

doi:10.1007/978-3-319-03841-4_33

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 proceeding › Conference 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 language	English (US)
Title of host publication	Graph Drawing - 21st International Symposium, GD 2013, Revised Selected Papers
Publisher	Springer
Pages	376-387
Number of pages	12
ISBN (Print)	9783319038407
DOIs	https://doi.org/10.1007/978-3-319-03841-4_33
State	Published - 2013
Externally published	Yes
Event	21st International Symposium on Graph Drawing, GD 2013 - Bordeaux, France Duration: Sep 23 2013 → Sep 25 2013

Publication series

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

Other

Other	21st International Symposium on Graph Drawing, GD 2013
Country/Territory	France
City	Bordeaux
Period	9/23/13 → 9/25/13

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/978-3-319-03841-4_33

Library availability

Discover UIUC Full Text

Cite this

Chan, T. M., Hoffmann, H. F., Kiazyk, S., & Lubiw, A. (2013). Minimum length embedding of planar graphs at fixed vertex locations. In Graph Drawing - 21st International Symposium, GD 2013, Revised Selected Papers (pp. 376-387). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8242 LNCS). Springer. https://doi.org/10.1007/978-3-319-03841-4_33

Minimum length embedding of planar graphs at fixed vertex locations. / Chan, Timothy M.; Hoffmann, Hella Franziska; Kiazyk, Stephen et al.
Graph Drawing - 21st International Symposium, GD 2013, Revised Selected Papers. Springer, 2013. p. 376-387 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8242 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chan, TM, Hoffmann, HF, Kiazyk, S & Lubiw, A 2013, Minimum length embedding of planar graphs at fixed vertex locations. in Graph Drawing - 21st International Symposium, GD 2013, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8242 LNCS, Springer, pp. 376-387, 21st International Symposium on Graph Drawing, GD 2013, Bordeaux, France, 9/23/13. https://doi.org/10.1007/978-3-319-03841-4_33

Chan TM, Hoffmann HF, Kiazyk S, Lubiw A. Minimum length embedding of planar graphs at fixed vertex locations. In Graph Drawing - 21st International Symposium, GD 2013, Revised Selected Papers. Springer. 2013. p. 376-387. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-03841-4_33

Chan, Timothy M. ; Hoffmann, Hella Franziska ; Kiazyk, Stephen et al. / Minimum length embedding of planar graphs at fixed vertex locations. Graph Drawing - 21st International Symposium, GD 2013, Revised Selected Papers. Springer, 2013. pp. 376-387 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2886e1be119343c1931a4d03eab8dfa5,

title = "Minimum length embedding of planar graphs at fixed vertex locations",

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.",

author = "Chan, {Timothy M.} and Hoffmann, {Hella Franziska} and Stephen Kiazyk and Anna Lubiw",

year = "2013",

doi = "10.1007/978-3-319-03841-4_33",

language = "English (US)",

isbn = "9783319038407",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "376--387",

booktitle = "Graph Drawing - 21st International Symposium, GD 2013, Revised Selected Papers",

address = "Germany",

}

TY - GEN

T1 - Minimum length embedding of planar graphs at fixed vertex locations

AU - Chan, Timothy M.

AU - Hoffmann, Hella Franziska

AU - Kiazyk, Stephen

AU - Lubiw, Anna

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84891843617&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84891843617&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-03841-4_33

DO - 10.1007/978-3-319-03841-4_33

M3 - Conference contribution

AN - SCOPUS:84891843617

SN - 9783319038407

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 376

EP - 387

BT - Graph Drawing - 21st International Symposium, GD 2013, Revised Selected Papers

PB - Springer

T2 - 21st International Symposium on Graph Drawing, GD 2013

Y2 - 23 September 2013 through 25 September 2013

ER -

Minimum length embedding of planar graphs at fixed vertex locations

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this