Proportional contact representations of planar graphs

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

doi:10.1007/978-3-642-25878-7_4

Proportional contact representations of planar graphs

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

Computer Science

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

9 Scopus citations

Abstract

We study contact representations for planar graphs, with vertices represented by simple polygons and adjacencies represented by point-contacts or side-contacts between the corresponding polygons. Specifically, we consider proportional contact representations, where pre-specified vertex weights must be represented by the areas of the corresponding polygons. Several natural optimization goals for such representations include minimizing the complexity of the polygons, the cartographic error, and the unused area. We describe constructive algorithms for proportional contact representations with optimal complexity for general planar graphs and planar 2-segment graphs, which include maximal outerplanar graphs and partial 2-trees.

Original language	English (US)
Title of host publication	Graph Drawing - 19th International Symposium, GD 2011, Revised Selected Papers
Pages	26-38
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-642-25878-7_4
State	Published - 2012
Event	19th International Symposium on Graph Drawing, GD 2011 - Eindhoven, Netherlands Duration: Sep 21 2011 → Sep 23 2011

Publication series

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

Other

Other	19th International Symposium on Graph Drawing, GD 2011
Country/Territory	Netherlands
City	Eindhoven
Period	9/21/11 → 9/23/11

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-25878-7_4

Cite this

Alam, M. J., Biedl, T., Felsner, S., Kaufmann, M., & Kobourov, S. G. (2012). Proportional contact representations of planar graphs. In Graph Drawing - 19th International Symposium, GD 2011, Revised Selected Papers (pp. 26-38). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7034 LNCS). https://doi.org/10.1007/978-3-642-25878-7_4

Proportional contact representations of planar graphs. / Alam, Muhammad Jawaherul; Biedl, Therese; Felsner, Stefan et al.
Graph Drawing - 19th International Symposium, GD 2011, Revised Selected Papers. 2012. p. 26-38 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7034 LNCS).

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

Alam, MJ, Biedl, T, Felsner, S, Kaufmann, M & Kobourov, SG 2012, Proportional contact representations of planar graphs. in Graph Drawing - 19th International Symposium, GD 2011, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7034 LNCS, pp. 26-38, 19th International Symposium on Graph Drawing, GD 2011, Eindhoven, Netherlands, 9/21/11. https://doi.org/10.1007/978-3-642-25878-7_4

Alam MJ, Biedl T, Felsner S, Kaufmann M, Kobourov SG. Proportional contact representations of planar graphs. In Graph Drawing - 19th International Symposium, GD 2011, Revised Selected Papers. 2012. p. 26-38. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-25878-7_4

@inproceedings{c2760644554a47229e4d28f59e0964a6,

title = "Proportional contact representations of planar graphs",

abstract = "We study contact representations for planar graphs, with vertices represented by simple polygons and adjacencies represented by point-contacts or side-contacts between the corresponding polygons. Specifically, we consider proportional contact representations, where pre-specified vertex weights must be represented by the areas of the corresponding polygons. Several natural optimization goals for such representations include minimizing the complexity of the polygons, the cartographic error, and the unused area. We describe constructive algorithms for proportional contact representations with optimal complexity for general planar graphs and planar 2-segment graphs, which include maximal outerplanar graphs and partial 2-trees.",

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

year = "2012",

doi = "10.1007/978-3-642-25878-7_4",

language = "English (US)",

isbn = "9783642258770",

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

pages = "26--38",

booktitle = "Graph Drawing - 19th International Symposium, GD 2011, Revised Selected Papers",

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

}

TY - GEN

T1 - Proportional contact representations of planar graphs

AU - Alam, Muhammad Jawaherul

AU - Biedl, Therese

AU - Felsner, Stefan

AU - Kaufmann, Michael

AU - Kobourov, Stephen G.

PY - 2012

Y1 - 2012

N2 - We study contact representations for planar graphs, with vertices represented by simple polygons and adjacencies represented by point-contacts or side-contacts between the corresponding polygons. Specifically, we consider proportional contact representations, where pre-specified vertex weights must be represented by the areas of the corresponding polygons. Several natural optimization goals for such representations include minimizing the complexity of the polygons, the cartographic error, and the unused area. We describe constructive algorithms for proportional contact representations with optimal complexity for general planar graphs and planar 2-segment graphs, which include maximal outerplanar graphs and partial 2-trees.

AB - We study contact representations for planar graphs, with vertices represented by simple polygons and adjacencies represented by point-contacts or side-contacts between the corresponding polygons. Specifically, we consider proportional contact representations, where pre-specified vertex weights must be represented by the areas of the corresponding polygons. Several natural optimization goals for such representations include minimizing the complexity of the polygons, the cartographic error, and the unused area. We describe constructive algorithms for proportional contact representations with optimal complexity for general planar graphs and planar 2-segment graphs, which include maximal outerplanar graphs and partial 2-trees.

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

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

U2 - 10.1007/978-3-642-25878-7_4

DO - 10.1007/978-3-642-25878-7_4

M3 - Conference contribution

AN - SCOPUS:84455182319

SN - 9783642258770

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

SP - 26

EP - 38

BT - Graph Drawing - 19th International Symposium, GD 2011, Revised Selected Papers

T2 - 19th International Symposium on Graph Drawing, GD 2011

Y2 - 21 September 2011 through 23 September 2011

ER -

Proportional contact representations of planar graphs

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this