Simultaneous embedding of a planar graph and its dual on the grid

Cesim Erten; Stephen G. Kobourov

doi:10.1007/3-540-36136-7_50

Simultaneous embedding of a planar graph and its dual on the grid

Cesim Erten
, Stephen G. Kobourov

Computer Science

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

7 Scopus citations

Abstract

Traditional representations of graphs and their duals suggest the requirement that the dual vertices should be placed inside their corresponding primal faces, and the edges of the dual graph should cross only their corresponding primal edges. We consider the problem of simultaneously embedding a planar graph and its dual on a small integer grid such that the edges are drawn as straight-line segments and the only crossings are between primal-dual pairs of edges. We provide an O(n) time algorithm that simultaneously embeds a 3-connected planar graph and its dual on a (2n - 2) × (2n - 2) integer grid, where n is the total number of vertices in the graph and its dual.

Original language	English (US)
Title of host publication	Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings
Pages	575-587
Number of pages	13
DOIs	https://doi.org/10.1007/3-540-36136-7_50
State	Published - 2002
Event	13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 - Vancouver, BC, Canada Duration: Nov 21 2002 → Nov 23 2002

Publication series

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

Other

Other	13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
Country/Territory	Canada
City	Vancouver, BC
Period	11/21/02 → 11/23/02

Keywords

Convex planar drawing
Graph drawing
Planar embedding
Simultaneous embedding

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-36136-7_50

Cite this

Erten, C., & Kobourov, S. G. (2002). Simultaneous embedding of a planar graph and its dual on the grid. In Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings (pp. 575-587). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2518 LNCS). https://doi.org/10.1007/3-540-36136-7_50

Simultaneous embedding of a planar graph and its dual on the grid. / Erten, Cesim; Kobourov, Stephen G.
Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. 2002. p. 575-587 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2518 LNCS).

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

Erten, C & Kobourov, SG 2002, Simultaneous embedding of a planar graph and its dual on the grid. in Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2518 LNCS, pp. 575-587, 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002, Vancouver, BC, Canada, 11/21/02. https://doi.org/10.1007/3-540-36136-7_50

@inproceedings{113397e450d4409a843e23f6e641af66,

title = "Simultaneous embedding of a planar graph and its dual on the grid",

abstract = "Traditional representations of graphs and their duals suggest the requirement that the dual vertices should be placed inside their corresponding primal faces, and the edges of the dual graph should cross only their corresponding primal edges. We consider the problem of simultaneously embedding a planar graph and its dual on a small integer grid such that the edges are drawn as straight-line segments and the only crossings are between primal-dual pairs of edges. We provide an O(n) time algorithm that simultaneously embeds a 3-connected planar graph and its dual on a (2n - 2) × (2n - 2) integer grid, where n is the total number of vertices in the graph and its dual.",

keywords = "Convex planar drawing, Graph drawing, Planar embedding, Simultaneous embedding",

author = "Cesim Erten and Kobourov, \{Stephen G.\}",

year = "2002",

doi = "10.1007/3-540-36136-7\_50",

language = "English (US)",

isbn = "3540001425",

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

pages = "575--587",

booktitle = "Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings",

note = "13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 ; Conference date: 21-11-2002 Through 23-11-2002",

}

TY - GEN

T1 - Simultaneous embedding of a planar graph and its dual on the grid

AU - Erten, Cesim

AU - Kobourov, Stephen G.

PY - 2002

Y1 - 2002

N2 - Traditional representations of graphs and their duals suggest the requirement that the dual vertices should be placed inside their corresponding primal faces, and the edges of the dual graph should cross only their corresponding primal edges. We consider the problem of simultaneously embedding a planar graph and its dual on a small integer grid such that the edges are drawn as straight-line segments and the only crossings are between primal-dual pairs of edges. We provide an O(n) time algorithm that simultaneously embeds a 3-connected planar graph and its dual on a (2n - 2) × (2n - 2) integer grid, where n is the total number of vertices in the graph and its dual.

AB - Traditional representations of graphs and their duals suggest the requirement that the dual vertices should be placed inside their corresponding primal faces, and the edges of the dual graph should cross only their corresponding primal edges. We consider the problem of simultaneously embedding a planar graph and its dual on a small integer grid such that the edges are drawn as straight-line segments and the only crossings are between primal-dual pairs of edges. We provide an O(n) time algorithm that simultaneously embeds a 3-connected planar graph and its dual on a (2n - 2) × (2n - 2) integer grid, where n is the total number of vertices in the graph and its dual.

KW - Convex planar drawing

KW - Graph drawing

KW - Planar embedding

KW - Simultaneous embedding

UR - https://www.scopus.com/pages/publications/84878641539

UR - https://www.scopus.com/pages/publications/84878641539#tab=citedBy

U2 - 10.1007/3-540-36136-7_50

DO - 10.1007/3-540-36136-7_50

M3 - Conference contribution

AN - SCOPUS:84878641539

SN - 3540001425

SN - 9783540001423

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

SP - 575

EP - 587

BT - Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings

T2 - 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002

Y2 - 21 November 2002 through 23 November 2002

ER -

Simultaneous embedding of a planar graph and its dual on the grid

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this