## 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 Ω(n^{2}) area. This bound is tight. If we use only straight channels, then outerplanar graphs with k ears may require Ω(min(nk, n^{2}/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 Ω(n^{7/6}) area.

Original language | English |
---|---|

Title of host publication | WALCOM: Algorithms and Computation - 11th International Conference and Workshops, WALCOM 2017, Proceedings |

Publisher | Springer |

Pages | 149-160 |

Number of pages | 12 |

ISBN (Print) | 9783319539249 |

DOIs | |

Publication status | Published - 2017 |

Event | 11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017) - Hsinchu, Taiwan Duration: 29 Mar 2017 → 31 Mar 2017 Conference number: 11 http://walcom2017.nctu.edu.tw/index.html |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 10167 |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Conference

Conference | 11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017) |
---|---|

Abbreviated title | WALCOM2017 |

Country/Territory | Taiwan |

City | Hsinchu |

Period | 29/03/17 → 31/03/17 |

Internet address |