On directed graphs with an upward straight-line embedding into every point set

Carla Binucci; Emilio Di Giacomo; Walter Didimo; Alejandro Estrella-Balderrama; Fabrizio Frati; Stephen G. Kobourov; Giuseppe Liotta

On directed graphs with an upward straight-line embedding into every point set

Carla Binucci, Emilio Di Giacomo, Walter Didimo, Alejandro Estrella-Balderrama, Fabrizio Frati, Stephen G. Kobourov, Giuseppe Liotta

Research output: Contribution to conference › Paper › peer-review

Abstract

In this paper we study the problem of computing an up- ward straight-line embedding of a directed graph G into a point set S, i.e. a planar drawing of G such that each vertex is mapped to a point of S, each edge is drawn as a straight-line segment, and all the edges are oriented according to a common direction. We characterize the family of directed graphs that admit an upward straight-line embedding into every one-side convex point set, that is, into every point-set such that the top-most and the bottom-most points are adjacent in the convex hull of the point set. Also we show how to construct up- ward straight-line embeddings for a sub-class of directed paths when the point set is in general position.

Original language	English (US)
Pages	21-24
Number of pages	4
State	Published - 2009
Externally published	Yes
Event	21st Annual Canadian Conference on Computational Geometry, CCCG 2009 - Vancouver, BC, Canada Duration: Aug 17 2009 → Aug 19 2009

Other

Other	21st Annual Canadian Conference on Computational Geometry, CCCG 2009
Country/Territory	Canada
City	Vancouver, BC
Period	8/17/09 → 8/19/09

ASJC Scopus subject areas

Computational Mathematics
Geometry and Topology

Cite this

@conference{89956144313c418583bc3a78630435c5,

title = "On directed graphs with an upward straight-line embedding into every point set",

abstract = "In this paper we study the problem of computing an up- ward straight-line embedding of a directed graph G into a point set S, i.e. a planar drawing of G such that each vertex is mapped to a point of S, each edge is drawn as a straight-line segment, and all the edges are oriented according to a common direction. We characterize the family of directed graphs that admit an upward straight-line embedding into every one-side convex point set, that is, into every point-set such that the top-most and the bottom-most points are adjacent in the convex hull of the point set. Also we show how to construct up- ward straight-line embeddings for a sub-class of directed paths when the point set is in general position.",

author = "Carla Binucci and {Di Giacomo}, Emilio and Walter Didimo and Alejandro Estrella-Balderrama and Fabrizio Frati and Kobourov, {Stephen G.} and Giuseppe Liotta",

year = "2009",

language = "English (US)",

pages = "21--24",

note = "21st Annual Canadian Conference on Computational Geometry, CCCG 2009 ; Conference date: 17-08-2009 Through 19-08-2009",

}

TY - CONF

T1 - On directed graphs with an upward straight-line embedding into every point set

AU - Binucci, Carla

AU - Di Giacomo, Emilio

AU - Didimo, Walter

AU - Estrella-Balderrama, Alejandro

AU - Frati, Fabrizio

AU - Kobourov, Stephen G.

AU - Liotta, Giuseppe

PY - 2009

Y1 - 2009

N2 - In this paper we study the problem of computing an up- ward straight-line embedding of a directed graph G into a point set S, i.e. a planar drawing of G such that each vertex is mapped to a point of S, each edge is drawn as a straight-line segment, and all the edges are oriented according to a common direction. We characterize the family of directed graphs that admit an upward straight-line embedding into every one-side convex point set, that is, into every point-set such that the top-most and the bottom-most points are adjacent in the convex hull of the point set. Also we show how to construct up- ward straight-line embeddings for a sub-class of directed paths when the point set is in general position.

AB - In this paper we study the problem of computing an up- ward straight-line embedding of a directed graph G into a point set S, i.e. a planar drawing of G such that each vertex is mapped to a point of S, each edge is drawn as a straight-line segment, and all the edges are oriented according to a common direction. We characterize the family of directed graphs that admit an upward straight-line embedding into every one-side convex point set, that is, into every point-set such that the top-most and the bottom-most points are adjacent in the convex hull of the point set. Also we show how to construct up- ward straight-line embeddings for a sub-class of directed paths when the point set is in general position.

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

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

M3 - Paper

AN - SCOPUS:84883046697

SP - 21

EP - 24

T2 - 21st Annual Canadian Conference on Computational Geometry, CCCG 2009

Y2 - 17 August 2009 through 19 August 2009

ER -

On directed graphs with an upward straight-line embedding into every point set

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this