72 research outputs found
Drawing Graphs by Example Efficiently: Trees and Planar Acyclic Digraphs (Extended Abstract)
No full text) Isabel F. Cruz 1 and Ashim Garg 2 1 Department of Electrical Engineering and Computer Science Tufts University Medford, MA 02155, USA 2 Department of Computer Science Brown University Providence, RI 02912--1910, USA Abstract. Constraint-based graph drawing systems provide expressive power and flexibility. Previously proposed approaches make use of general constraint solvers, which are inefficient, and of textual specification of constraints, which can be long and difficult to understand. In this paper we propose the use of a constraint-based visual language for constructing planar drawings of trees, series-parallel graphs, and acyclic digraphs in linear time. A graph drawing system based on our approach can therefore provide the power of constraint-based graph drawing, the simplicity of visual specifications, and the computational efficiency that is typical of the algorithmic-based approaches. 1 Introduction It is common practice to explain the layout of a graph using pictu..
“A legacy of troubles. Bengal Partition as long-lasting narration”
No full textThis essays analyses Indian Partition Literature, focusing on the Eastern border and the novel East/West by the Bengali author Gangopadhyay
On Drawing Angle Graphs (Extended Abstract)
No full textAn Angle graph is a graph with a fixed cyclic order of edges around each vertex and an angle specified for every pair of consecutive edges incident on each vertex. We study the problem of constructing a drawing of an angle graph that preserves its angles, and present several new results
New results on drawing angle graphs
No full textAbstractAn angle graph is a graph with a fixed cyclic order of the edges around each vertex and an angle specified for every pair of consecutive edges incident on a vertex. We study the problem of constructing a drawing of an angle graph that preserves its angles, and present several new results. •• We disprove the conjectures of Vijayan (1986) about the relationship between the planarity of an angle graph and the planarity of its biconnected components.•• We show that testing an angle graph for planarity is NP-hard.•• Using our NP-hardness result, we show that given a triconnected planar graph and an angle α, the problem of determining whether it admits a planar straight-line drawing in which the angle between any two consecutive edges incident on the same vertex is at least α, is NP-hard.•• A multilayered angle graph is one whose edges are assigned to a given set of layers. A multilayered angle graph is multiplanar if it admits a drawing in which edges assigned to the same layer do not cross. We prove that testing a multilayered angle graph for multiplanarity is NP-hard even if we restrict the angles to be multiples of 90° and the number of layers to two.•• We give a simple linear time algorithm for testing whether a series-parallel angle graph admits a (nonplanar) drawing that preserves its angles
Area-Efficient Drawings of Outerplanar Graphs
No full textWe show that an outerplanar graph G with n vertices and degree d admits a planar straight-line grid drawing with area O(dn^{1.48}) in O(n) time. This implies that if d =o(n^{0.52}), then G can be drawn in this fashion in o(n^2) area
Almost Bend-Optimal Planar Orthogonal Drawings of Biconnected Degree-3 Planar Graphs in Quadratic Time
No full textLet G be a degree-3 planar biconnected graph with n vertices. Let Opt(G) be the minimum number of bends in any orthogonal planar drawing of G. We show that G admits a planar orthogonal drawing D with at most Opt(G)+3 bends that can constructed in O(n^{2}) time. The fastest known algorithm for constructing a bend-minimum drawing of G has time-complexity O(n^{5} log n) and therefore, we present a significantly faster algorithm that constructs almost bend-optimal drawings
Compact Encodings of Planar Orthogonal Drawings
No full textWe present time-efficient algorithms for encoding (and decoding) planar orthogonal drawings of degree-4 and degree-3 biconnected and triconnected planar graphs using small number of bits. We also present time-efficient algorithms for encoding (and decoding) turn-monotone planar orthogonal drawings
- …
