Linear-time algorithms for hole-free rectilinear proportional contact graph representations

Muhammad Jawaherul Alam; Therese Biedl; Stefan Felsner; Andreas Gerasch; Michael Kaufmann; Stephen G. Kobourov

doi:10.1007/978-3-642-25591-5_30

Linear-time algorithms for hole-free rectilinear proportional contact graph representations

Muhammad Jawaherul Alam, Therese Biedl, Stefan Felsner, Andreas Gerasch, Michael Kaufmann, Stephen G. Kobourov

Computer Science

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

9 Scopus citations

Abstract

In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. In this paper we study proportional contact representations that use rectilinear polygons without wasted areas (white space). In this setting, the best known algorithm for proportional contact representation of a maximal planar graph uses 12-sided rectilinear polygons and takes O(nlogn) time. We describe a new algorithm that guarantees 10-sided rectilinear polygons and runs in O(n) time. We also describe a linear-time algorithm for proportional contact representation of planar 3-trees with 8-sided rectilinear polygons and show that this is optimal, as there exist planar 3-trees that require 8-sided polygons. Finally, we show that a maximal outer-planar graph admits a proportional contact representation using rectilinear polygons with 6 sides when the outer-boundary is a rectangle and with 4 sides otherwise.

Original language	English (US)
Title of host publication	Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings
Pages	281-291
Number of pages	11
DOIs	https://doi.org/10.1007/978-3-642-25591-5_30
State	Published - 2011
Event	22nd International Symposium on Algorithms and Computation, ISAAC 2011 - Yokohama, Japan Duration: Dec 5 2011 → Dec 8 2011

Publication series

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

Other

Other	22nd International Symposium on Algorithms and Computation, ISAAC 2011
Country/Territory	Japan
City	Yokohama
Period	12/5/11 → 12/8/11

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-25591-5_30

Cite this

Alam, M. J., Biedl, T., Felsner, S., Gerasch, A., Kaufmann, M., & Kobourov, S. G. (2011). Linear-time algorithms for hole-free rectilinear proportional contact graph representations. In Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings (pp. 281-291). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7074 LNCS). https://doi.org/10.1007/978-3-642-25591-5_30

Linear-time algorithms for hole-free rectilinear proportional contact graph representations. / Alam, Muhammad Jawaherul; Biedl, Therese; Felsner, Stefan et al.
Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings. 2011. p. 281-291 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7074 LNCS).

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

Alam, MJ, Biedl, T, Felsner, S, Gerasch, A, Kaufmann, M & Kobourov, SG 2011, Linear-time algorithms for hole-free rectilinear proportional contact graph representations. in Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7074 LNCS, pp. 281-291, 22nd International Symposium on Algorithms and Computation, ISAAC 2011, Yokohama, Japan, 12/5/11. https://doi.org/10.1007/978-3-642-25591-5_30

Alam MJ, Biedl T, Felsner S, Gerasch A, Kaufmann M, Kobourov SG. Linear-time algorithms for hole-free rectilinear proportional contact graph representations. In Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings. 2011. p. 281-291. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-25591-5_30

Alam, Muhammad Jawaherul ; Biedl, Therese ; Felsner, Stefan et al. / Linear-time algorithms for hole-free rectilinear proportional contact graph representations. Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings. 2011. pp. 281-291 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8e951fa32a6944eca93d248596a24abf,

title = "Linear-time algorithms for hole-free rectilinear proportional contact graph representations",

abstract = "In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. In this paper we study proportional contact representations that use rectilinear polygons without wasted areas (white space). In this setting, the best known algorithm for proportional contact representation of a maximal planar graph uses 12-sided rectilinear polygons and takes O(nlogn) time. We describe a new algorithm that guarantees 10-sided rectilinear polygons and runs in O(n) time. We also describe a linear-time algorithm for proportional contact representation of planar 3-trees with 8-sided rectilinear polygons and show that this is optimal, as there exist planar 3-trees that require 8-sided polygons. Finally, we show that a maximal outer-planar graph admits a proportional contact representation using rectilinear polygons with 6 sides when the outer-boundary is a rectangle and with 4 sides otherwise.",

author = "Alam, {Muhammad Jawaherul} and Therese Biedl and Stefan Felsner and Andreas Gerasch and Michael Kaufmann and Kobourov, {Stephen G.}",

year = "2011",

doi = "10.1007/978-3-642-25591-5_30",

language = "English (US)",

isbn = "9783642255908",

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

pages = "281--291",

booktitle = "Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings",

note = "22nd International Symposium on Algorithms and Computation, ISAAC 2011 ; Conference date: 05-12-2011 Through 08-12-2011",

}

TY - GEN

T1 - Linear-time algorithms for hole-free rectilinear proportional contact graph representations

AU - Alam, Muhammad Jawaherul

AU - Biedl, Therese

AU - Felsner, Stefan

AU - Gerasch, Andreas

AU - Kaufmann, Michael

AU - Kobourov, Stephen G.

PY - 2011

Y1 - 2011

N2 - In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. In this paper we study proportional contact representations that use rectilinear polygons without wasted areas (white space). In this setting, the best known algorithm for proportional contact representation of a maximal planar graph uses 12-sided rectilinear polygons and takes O(nlogn) time. We describe a new algorithm that guarantees 10-sided rectilinear polygons and runs in O(n) time. We also describe a linear-time algorithm for proportional contact representation of planar 3-trees with 8-sided rectilinear polygons and show that this is optimal, as there exist planar 3-trees that require 8-sided polygons. Finally, we show that a maximal outer-planar graph admits a proportional contact representation using rectilinear polygons with 6 sides when the outer-boundary is a rectangle and with 4 sides otherwise.

AB - In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. In this paper we study proportional contact representations that use rectilinear polygons without wasted areas (white space). In this setting, the best known algorithm for proportional contact representation of a maximal planar graph uses 12-sided rectilinear polygons and takes O(nlogn) time. We describe a new algorithm that guarantees 10-sided rectilinear polygons and runs in O(n) time. We also describe a linear-time algorithm for proportional contact representation of planar 3-trees with 8-sided rectilinear polygons and show that this is optimal, as there exist planar 3-trees that require 8-sided polygons. Finally, we show that a maximal outer-planar graph admits a proportional contact representation using rectilinear polygons with 6 sides when the outer-boundary is a rectangle and with 4 sides otherwise.

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

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

U2 - 10.1007/978-3-642-25591-5_30

DO - 10.1007/978-3-642-25591-5_30

M3 - Conference contribution

AN - SCOPUS:84055200211

SN - 9783642255908

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

SP - 281

EP - 291

BT - Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings

T2 - 22nd International Symposium on Algorithms and Computation, ISAAC 2011

Y2 - 5 December 2011 through 8 December 2011

ER -

Linear-time algorithms for hole-free rectilinear proportional contact graph representations

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this