1,721,095 research outputs found
Special issue with selected papers from the 20th international symposium on graph drawing, GD 2012: Guest editors' foreword.
No full text
Drawing Database Schemas
No full textA wide number of practical applications would benefit from automatically generated graphical representations of database schemas, in which tables are represented by boxes, and table attributes correspond to distinct stripes inside each table. Links, connecting attributes of two different tables, represent referential constraints or join relationships, and may attach arbitrarily to the left- or to the right hand side of the stripes representing the attributes. To our knowledge no drawing technique is available to automatically produce diagrams in such a strongly constrained drawing convention. In this paper we provide a polynomial time algorithm for solving this problem, and test its efficiency and effectiveness against a large test suite. Also, we describe an implementation of a system that uses such an algorithm and we study the main methodological problems we faced in developing such a technology
Upward and Quasi-Upward Planarity Testing of Embedded Mixed Graphs
No full textMixed graphs have both directed and undirected edges and have received considerable attention in the literature. We study two upward planarity testing problems for embedded mixed graphs, give some NP-hardness results, and describe Integer Linear Programming techniques to solve them. Experiments show the efficiency of our approach
Upward Embeddings and Orientations of Undirected Planar Graphs
No full textAn upward embedding of an embedded planar graph specifies, for each vertex v, which edges are incident on v "above" or "below" and, in turn, induces an upward orientation of the edges from bottom to top. In this paper we characterize the set of all upward embeddings and orientations of an embedded planar graph by using a simple flow model, which is related to that described by Bousset [] to characterize bipolar orientations. We take advantage of such a flow model to compute upward orientations with the minimum number of sources and sinks of 1-connected embedded planar graphs. We finally devise a new algorithm for computing visibility representations of 1-connected planar graphs using our theoretic results.
Quasi-Upward planarity (extended abstract)
No full textIn this paper we introduce the quasi-upward planar drawing convention and give a polynomial time algorithm for computing a quasi-upward planar drawing with a minimum number of bends within a given planar embedding. Further, we study the problem of computing quasi-upward planar drawings with a minimum number of bends of digraphs considering all the possible planar embeddings. The paper contains also experimental results about proposed techniques
- …
