In this paper we study the problem of computing homothetic triangle contact representations of planar graphs. Since not all planar graphs admit such a representation, we concentrate on meaningful subfamilies of planar graphs and prove that: (i) every two-terminal series-parallel digraph has a homothetic triangle contact representation, which can be computed in linear time; (ii) every partial planar 3-tree admits a homothetic triangle contact representation.
Homotetic Triangle Contact Representations of Planar Graphs
BINUCCI, Carla;DI GIACOMO, Emilio;DIDIMO, WALTER;
2007
Abstract
In this paper we study the problem of computing homothetic triangle contact representations of planar graphs. Since not all planar graphs admit such a representation, we concentrate on meaningful subfamilies of planar graphs and prove that: (i) every two-terminal series-parallel digraph has a homothetic triangle contact representation, which can be computed in linear time; (ii) every partial planar 3-tree admits a homothetic triangle contact representation.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
