<p> A graph G is called <i>planar</i> if it can be drawn on the plan such that no two distinct edges intersect each other but at common endpoints. Such drawing is called a plane embedding of <i>G.</i> A plane graph is a graph with a fixed embedding. A straight-line drawing <i>G</i> of a graph <i>G</i> = (<i>V, E</i>) is a drawing where each vertex of <i>V</i> is drawn as a distinct point on the plane and each edge of <i>G</i> is drawn as a line segment connecting two end vertices. In this thesis, we study a set of planar graph drawing problems. </p><p> First, we consider the problem of <i>monotone drawing:</i> A path <i>P</i> in a straight line drawing Γ is <i>monotone </i> if there exists a line l such that the orthogonal projections of the vertices of P on l appear along l in the order they appear in <i> P.</i> We call l a monotone line (or <i>monotone direction</i>) of <i>P. G</i> is called a monotone drawing of <i> G</i> if it contains at least one monotone path <i>P<sub>uw</sub></i> between every pair of vertices <i>u,w</i> of <i>G.</i> Monotone drawings were recently introduced by Angelini et al. and represent a new visualization paradigm, and is also closely related to several other important graph drawing problems. As in many graph drawing problems, one of the main concerns of this research is to reduce the drawing size, which is the size of the smallest integer grid such that every graph in the graph class can be drawn in such a grid. We present two approaches for the problem of monotone drawings of trees. Our first approach show that every <i>n</i>-vertex tree <i>T</i> admits a monotone drawing on a grid of size <i> O</i>(<i>n</i><sup>1.205</sup>) × <i>O</i>(<i> n</i><sup>1.205</sup>) grid. Our second approach further reduces the size of drawing to 12n × 12n, which is asymptotically optimal. Both of our two drawings can be constructed in <i>O(n)</i> time.</p><p> We also consider monotone drawings of 3-connected plane graphs. We prove that the classical Schnyder drawing of 3-connected plane graphs is a monotone drawing on a <i>f × f</i> grid, which can be constructed in <i> O(n)</i> time. </p><p> Second, we consider the problem of orthogonal drawing. An <i>orthogonal drawing</i> of a plane graph <i>G</i> is a planar drawing of <i> G</i> such that each vertex of <i>G</i> is drawn as a point on the plane, and each edge is drawn as a sequence of horizontal and vertical line segments with no crossings. Orthogonal drawing has attracted much attention due to its various applications in circuit schematics, relationship diagrams, data flow diagrams etc. . Rahman et al. gave a necessary and sufficient condition for a plane graph <i>G</i> of maximum degree 3 to have an orthogonal drawing without bends. An orthogonal drawing <i>D(G)</i> is <i> orthogonally</i> convex if all faces of <i>D(G)</i> are orthogonally convex polygons. Chang et al. gave a necessary and sufficient condition (which strengthens the conditions in the previous result) for a plane graph <i> G</i> of maximum degree 3 to have an orthogonal convex drawing without bends. We further strengthen the results such that if <i>G</i> satisfies the same conditions as in previous papers, it not only has an orthogonally convex drawing, but also a stronger star-shaped orthogonal drawing.</p><p>
| Identifer | oai:union.ndltd.org:PROQUEST/oai:pqdtoai.proquest.com:10284151 |
| Date | 08 August 2017 |
| Creators | He, Dayu |
| Publisher | State University of New York at Buffalo |
| Source Sets | ProQuest.com |
| Language | English |
| Detected Language | English |
| Type | thesis |
Page generated in 0.0017 seconds