Dot product representations of planar graphs

Ross J. Kang; Tobias Müller

doi:10.1007/978-3-642-18469-7_26

Dot product representations of planar graphs

Ross J. Kang, Tobias Müller

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

A graph G on n vertices is a k-dot product graph if there are vectors u 1 ,…,u n ∈R k , one for each vertex of G, such that u T i u j ≥1 if and only if ij ∈ E(G). Fiduccia, Scheinerman, Trenk and Zito (1998) asked whether every planar graph is a 3-dot product graph. We show that the answer is “no”. On the other hand, every planar graph is a 4-dot product graph.

Original language	English
Title of host publication	Graph drawing
Subtitle of host publication	18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010. Revised Selected Papers
Editors	Ulrik Brandes, Sabine Cornelsen
Publisher	Springer
Pages	287-292
Number of pages	6
ISBN (Electronic)	978-3-642-18469-7
ISBN (Print)	978-3-642-18468-0
DOIs	https://doi.org/10.1007/978-3-642-18469-7_26
Publication status	Published - 2011
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science
Volume	6502
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-642-18469-7_26

http://dx.doi.org/10.1007/978-3-642-18469-7_26

Cite this

@inproceedings{2625041f325841739d7282970989a9ac,

title = "Dot product representations of planar graphs",

abstract = "A graph G on n vertices is a k-dot product graph if there are vectors u 1 ,…,u n ∈R k , one for each vertex of G, such that u T i u j ≥1 if and only if ij ∈ E(G). Fiduccia, Scheinerman, Trenk and Zito (1998) asked whether every planar graph is a 3-dot product graph. We show that the answer is “no”. On the other hand, every planar graph is a 4-dot product graph.",

author = "Kang, {Ross J.} and Tobias M{\"u}ller",

year = "2011",

doi = "10.1007/978-3-642-18469-7_26",

language = "English",

isbn = "978-3-642-18468-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "287--292",

editor = "Brandes, {Ulrik } and Cornelsen, {Sabine }",

booktitle = "Graph drawing",

address = "Germany",

}

Dot product representations of planar graphs. / Kang, Ross J.; Müller, Tobias.
Graph drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010. Revised Selected Papers. ed. / Ulrik Brandes; Sabine Cornelsen. Springer, 2011. p. 287-292 (Lecture Notes in Computer Science; Vol. 6502).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Dot product representations of planar graphs

AU - Kang, Ross J.

AU - Müller, Tobias

PY - 2011

Y1 - 2011

N2 - A graph G on n vertices is a k-dot product graph if there are vectors u 1 ,…,u n ∈R k , one for each vertex of G, such that u T i u j ≥1 if and only if ij ∈ E(G). Fiduccia, Scheinerman, Trenk and Zito (1998) asked whether every planar graph is a 3-dot product graph. We show that the answer is “no”. On the other hand, every planar graph is a 4-dot product graph.

AB - A graph G on n vertices is a k-dot product graph if there are vectors u 1 ,…,u n ∈R k , one for each vertex of G, such that u T i u j ≥1 if and only if ij ∈ E(G). Fiduccia, Scheinerman, Trenk and Zito (1998) asked whether every planar graph is a 3-dot product graph. We show that the answer is “no”. On the other hand, every planar graph is a 4-dot product graph.

U2 - 10.1007/978-3-642-18469-7_26

DO - 10.1007/978-3-642-18469-7_26

M3 - Conference contribution

SN - 978-3-642-18468-0

T3 - Lecture Notes in Computer Science

SP - 287

EP - 292

BT - Graph drawing

A2 - Brandes, Ulrik

A2 - Cornelsen, Sabine

PB - Springer

ER -

Dot product representations of planar graphs

Abstract

Publication series

Access to Document

Fingerprint

Cite this