Touching triangle representations for 3-connected planar graphs

Stephen G. Kobourov; Debajyoti Mondal; Rahnuma Islam Nishat

doi:10.1007/978-3-642-36763-2_18

Touching triangle representations for 3-connected planar graphs

Stephen G. Kobourov
, Debajyoti Mondal
, Rahnuma Islam Nishat

Computer Science

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

10 Scopus citations

Abstract

A touching triangle graph (TTG) representation of a planar graph is a planar drawing Γ of the graph, where each vertex is represented as a triangle and each edge e is represented as a side contact of the triangles that correspond to the end vertices of e. We call Γ a proper TTG representation if Γ determines a tiling of a triangle, where each tile corresponds to a distinct vertex of the input graph. In this paper we prove that every 3-connected cubic planar graph admits a proper TTG representation. We also construct proper TTG representations for parabolic grid graphs and the graphs determined by rectangular grid drawings (e.g., square grid graphs). Finally, we describe a fixed-parameter tractable decision algorithm for testing whether a 3-connected planar graph admits a proper TTG representation.

Original language	English (US)
Title of host publication	Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers
Pages	199-210
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-36763-2_18
State	Published - 2013
Event	20th International Symposium on Graph Drawing, GD 2012 - Redmond, WA, United States Duration: Sep 19 2012 → Sep 21 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7704 LNCS

Other

Other	20th International Symposium on Graph Drawing, GD 2012
Country/Territory	United States
City	Redmond, WA
Period	9/19/12 → 9/21/12

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-36763-2_18

Cite this

Kobourov, S. G., Mondal, D., & Nishat, R. I. (2013). Touching triangle representations for 3-connected planar graphs. In Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers (pp. 199-210). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7704 LNCS). https://doi.org/10.1007/978-3-642-36763-2_18

Touching triangle representations for 3-connected planar graphs. / Kobourov, Stephen G.; Mondal, Debajyoti; Nishat, Rahnuma Islam.
Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers. 2013. p. 199-210 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7704 LNCS).

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

Kobourov, SG, Mondal, D & Nishat, RI 2013, Touching triangle representations for 3-connected planar graphs. in Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7704 LNCS, pp. 199-210, 20th International Symposium on Graph Drawing, GD 2012, Redmond, WA, United States, 9/19/12. https://doi.org/10.1007/978-3-642-36763-2_18

@inproceedings{ae1b95aacf5940919ab7617c0a90df15,

title = "Touching triangle representations for 3-connected planar graphs",

abstract = "A touching triangle graph (TTG) representation of a planar graph is a planar drawing Γ of the graph, where each vertex is represented as a triangle and each edge e is represented as a side contact of the triangles that correspond to the end vertices of e. We call Γ a proper TTG representation if Γ determines a tiling of a triangle, where each tile corresponds to a distinct vertex of the input graph. In this paper we prove that every 3-connected cubic planar graph admits a proper TTG representation. We also construct proper TTG representations for parabolic grid graphs and the graphs determined by rectangular grid drawings (e.g., square grid graphs). Finally, we describe a fixed-parameter tractable decision algorithm for testing whether a 3-connected planar graph admits a proper TTG representation.",

author = "Kobourov, \{Stephen G.\} and Debajyoti Mondal and Nishat, \{Rahnuma Islam\}",

year = "2013",

doi = "10.1007/978-3-642-36763-2\_18",

language = "English (US)",

isbn = "9783642367625",

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

pages = "199--210",

booktitle = "Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers",

note = "20th International Symposium on Graph Drawing, GD 2012 ; Conference date: 19-09-2012 Through 21-09-2012",

}

TY - GEN

T1 - Touching triangle representations for 3-connected planar graphs

AU - Kobourov, Stephen G.

AU - Mondal, Debajyoti

AU - Nishat, Rahnuma Islam

PY - 2013

Y1 - 2013

N2 - A touching triangle graph (TTG) representation of a planar graph is a planar drawing Γ of the graph, where each vertex is represented as a triangle and each edge e is represented as a side contact of the triangles that correspond to the end vertices of e. We call Γ a proper TTG representation if Γ determines a tiling of a triangle, where each tile corresponds to a distinct vertex of the input graph. In this paper we prove that every 3-connected cubic planar graph admits a proper TTG representation. We also construct proper TTG representations for parabolic grid graphs and the graphs determined by rectangular grid drawings (e.g., square grid graphs). Finally, we describe a fixed-parameter tractable decision algorithm for testing whether a 3-connected planar graph admits a proper TTG representation.

AB - A touching triangle graph (TTG) representation of a planar graph is a planar drawing Γ of the graph, where each vertex is represented as a triangle and each edge e is represented as a side contact of the triangles that correspond to the end vertices of e. We call Γ a proper TTG representation if Γ determines a tiling of a triangle, where each tile corresponds to a distinct vertex of the input graph. In this paper we prove that every 3-connected cubic planar graph admits a proper TTG representation. We also construct proper TTG representations for parabolic grid graphs and the graphs determined by rectangular grid drawings (e.g., square grid graphs). Finally, we describe a fixed-parameter tractable decision algorithm for testing whether a 3-connected planar graph admits a proper TTG representation.

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

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

U2 - 10.1007/978-3-642-36763-2_18

DO - 10.1007/978-3-642-36763-2_18

M3 - Conference contribution

SN - 9783642367625

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

SP - 199

EP - 210

BT - Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers

T2 - 20th International Symposium on Graph Drawing, GD 2012

Y2 - 19 September 2012 through 21 September 2012

ER -

Touching triangle representations for 3-connected planar graphs

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this