Complexity measures for mosaic drawings

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

253 Downloads (Pure)

Abstract

Graph Drawing uses a well established set of complexity measures to determine the quality of a drawing, most notably the area of the drawing and the complexity of the edges. For contact representations the complexity of the shapes representing vertices also clearly contributes to the complexity of the drawing. Furthermore, if a contact representation does not fill its bounding shape completely, then also the complexity of its complement is visually salient. We study the complexity of contact representations with variable shapes, specifically mosaic drawings.Mosaic drawings are drawn on a tiling of the plane and represent vertices by configurations: simply-connected sets of tiles. The complement of a mosaic drawing with respect to its bounding rectangle is also a set of simply-connected tiles, the channels. We prove that simple mosaic drawings without channels may require Ω(n2) area. This bound is tight. If we use only straight channels, then outerplanar graphs with k ears may require Ω(min(nk, n2/k)) area. This bound is partially tight: we show how to draw outerplanar graphs with k ears in O(nk) area with L-shaped vertex configurations and straight channels. Finally, we argue that L-shaped channels are strictly more powerful than straight channels, but may still require Ω(n7/6) area.

Original languageEnglish
Title of host publicationWALCOM: Algorithms and Computation - 11th International Conference and Workshops, WALCOM 2017, Proceedings
PublisherSpringer
Pages149-160
Number of pages12
ISBN (Print)9783319539249
DOIs
Publication statusPublished - 2017
Event11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017) - Hsinchu, Taiwan
Duration: 29 Mar 201731 Mar 2017
Conference number: 11
http://walcom2017.nctu.edu.tw/index.html

Publication series

NameLecture Notes in Computer Science
Volume10167
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017)
Abbreviated titleWALCOM2017
Country/TerritoryTaiwan
CityHsinchu
Period29/03/1731/03/17
Internet address

Fingerprint

Dive into the research topics of 'Complexity measures for mosaic drawings'. Together they form a unique fingerprint.

Cite this