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
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

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{ed653d3f2f5d4ffb97eaaaf1a8aacb90,

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 - http://www.scopus.com/inward/record.url?scp=84874129237&partnerID=8YFLogxK

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

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

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

M3 - Conference contribution

AN - SCOPUS:84874129237

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