On touching triangle graphs

Emden R. Gansner, Yifan Hu, Stephen G. Kobourov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

Abstract

In this paper, we consider the problem of representing graphs by triangles whose sides touch. We present linear time algorithms for creating touching triangles representations for outerplanar graphs, square grid graphs, and hexagonal grid graphs. The class of graphs with touching triangles representations is not closed under minors, making characterization difficult. We do show that pairs of vertices can only have a small common neighborhood, and we present a complete characterization of the subclass of biconnected graphs that can be represented as triangulations of some polygon.

Original languageEnglish (US)
Title of host publicationGraph Drawing - 18th International Symposium, GD 2010, Revised Selected Papers
Pages250-261
Number of pages12
DOIs
StatePublished - 2011
Event18th International Symposium on Graph Drawing, GD 2010 - Konstanz, Germany
Duration: Sep 21 2010Sep 24 2010

Publication series

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

Other

Other18th International Symposium on Graph Drawing, GD 2010
Country/TerritoryGermany
CityKonstanz
Period9/21/109/24/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'On touching triangle graphs'. Together they form a unique fingerprint.

Cite this