Survey on Convex Drawing of Planar Graph
---
paper_title: Convex Grid Drawings of 3-Connected Planar Graphs

paper_content:

We consider the problem of embedding the vertices of a plane graph into a small (polynomial size) grid in the plane in such a way that the edges are straight, nonintersecting line segments and faces are convex polygons. We present a linear-time algorithm which, given an n-vertex 3-connected plane G (with n ≥ 3), finds such a straight-line convex embedding of G into a (n - 2) × (n - 2) grid.
---
paper_title: Convex Drawings of Hierarchical Planar Graphs and Clustered Planar Graphs

paper_content:

In this paper, we present results on convex drawings of hierarchical graphs and clustered graphs. A convex drawing is a planar straight-line drawing of a plane graph, where every facial cycle is drawn as a convex polygon. Hierarchical graphs and clustered graphs are useful graph models with structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. We first present the necessary and sufficient conditions for a hierarchical plane graph to admit a convex drawing. More specifically, we show that the necessary and sufficient conditions for a biconnected plane graph due to Thomassen [C. Thomassen, Plane representations of graphs, in: J.A. Bondy, U.S.R. Murty (Eds.), Progress in Graph Theory, Academic Press, 1984, pp. 43-69] remains valid for the case of a hierarchical plane graph. We then prove that every internally triconnected clustered plane graph with a completely connected clustering structure admits a ''fully convex drawing,'' a planar straight-line drawing such that both clusters and facial cycles are drawn as convex polygons. We also present algorithms to construct such convex drawings of hierarchical graphs and clustered graphs.
---
paper_title: Convex Grid Drawings of Four-Connected Plane Graphs

paper_content:

A convex grid drawing of a plane graph G is a drawing of G on the plane so that all vertices of G are put on grid points, all edges are drawn as straight-line segments between their endpoints without any edge-intersection, and every face boundary is a convex polygon. In this paper we give a linear-time algorithm for finding a convex grid drawing of any 4-connected plane graph G with four or more vertices on the outer face boundary. The algorithm yields a drawing in an integer grid such that W + H ≤ n - 1 if G has n vertices, where W is the width and H is the height of the grid. Thus the area W × H of the grid is at most ⌈(n - 1)/2⌉ ċ ⌊(n - 1)/2⌋. Our bounds on the grid sizes are optimal in the sense that there exist an infinite number of 4-connected plane graphs whose convex drawings need grids such that W + H = n - 1 and W × H = ⌈(n - 1)/2⌉ ċ ⌊(n - 1)/2⌋.
---
paper_title: Strictly convex drawings of planar graphs

paper_content:

Every three-connected planar graph with n vertices has a drawing on an O(n(2)) x O(n(2)) grid in which all faces are strictly convex polygons. These drawings are obtained by perturbing (not strictly) convex drawings on O(n) x O(n) grids. Tighter bounds are obtained when the faces have fewer sides. In the proof, we derive an explicit lower bound on the number of primitive vectors in a triangle.
---
paper_title: Convex Drawings of 3-Connected Plane Graphs

paper_content:

We use Schnyder woods of 3-connected planar graphs to produce convex straight-line drawings on a grid of size $(n-2-\Delta)\times (n-2-\Delta).$ The parameter $\Delta\geq 0$ depends on the Schnyder wood used for the drawing. This parameter is in the range $0 \leq \Delta\leq {n}/{2}-2.$ The algorithm is a refinement of the face-counting algorithm; thus, in particular, the size of the grid is at most $(f-2)\times(f-2).$ The above bound on the grid size simultaneously matches or improves all previously known bounds for convex drawings, in particular Schnyder's and the recent Zhang and He bound for triangulations and the Chrobak and Kant bound for 3-connected planar graphs. The algorithm takes linear time. The drawing algorithm has been implemented and tested. The expected grid size for the drawing of a random triangulation is close to $\frac{7}{8}n\times\frac{7}{8}n.$ For a random 3-connected plane graph, tests show that the expected size of the drawing is $\frac{3}{4}n\times\frac{3}{4}n.$
---
paper_title: Convex Drawings of Plane Graphs of Minimum Outer Apices

paper_content:

In a convex drawing of a plane graph G, every facial cycle of G is drawn as a convex polygon. A polygon for the outer facial cycle is called an outer convex polygon. A necessary and sufficient condition for a plane graph G to have a convex drawing is known. However, it has not been known how many apices of an outer convex polygon are necessary for G to have a convex drawing. In this paper, we show that the minimum number of apices of an outer convex polygon necessary for G to have a convex drawing is, in effect, equal to the number of leaves in a triconnected component decomposition tree of a new graph constructed from G, and that a convex drawing of G having the minimum number of apices can be found in linear time.
---
paper_title: Convex drawings of graphs with non-convex boundary

paper_content:

In this paper, we study a new problem of finding a convex drawing of graphs with a non-convex boundary. It is proved that every triconnected plane graph whose boundary is fixed with a star-shaped polygon admits a drawing in which every inner facial cycle is drawn as a convex polygon. Such a drawing, called an inner-convex drawing, can be obtained in linear time.
---
paper_title: Convex drawings of graphs with non-convex boundary

paper_content:

In this paper, we study a new problem of finding a convex drawing of graphs with a non-convex boundary. It is proved that every triconnected plane graph whose boundary is fixed with a star-shaped polygon admits a drawing in which every inner facial cycle is drawn as a convex polygon. Such a drawing, called an inner-convex drawing, can be obtained in linear time.
---
paper_title: Convex drawings of graphs with non-convex boundary

paper_content:

In this paper, we study a new problem of finding a convex drawing of graphs with a non-convex boundary. It is proved that every triconnected plane graph whose boundary is fixed with a star-shaped polygon admits a drawing in which every inner facial cycle is drawn as a convex polygon. Such a drawing, called an inner-convex drawing, can be obtained in linear time.
---
paper_title: Convex Drawings of Hierarchical Planar Graphs and Clustered Planar Graphs

paper_content:

In this paper, we present results on convex drawings of hierarchical graphs and clustered graphs. A convex drawing is a planar straight-line drawing of a plane graph, where every facial cycle is drawn as a convex polygon. Hierarchical graphs and clustered graphs are useful graph models with structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. We first present the necessary and sufficient conditions for a hierarchical plane graph to admit a convex drawing. More specifically, we show that the necessary and sufficient conditions for a biconnected plane graph due to Thomassen [C. Thomassen, Plane representations of graphs, in: J.A. Bondy, U.S.R. Murty (Eds.), Progress in Graph Theory, Academic Press, 1984, pp. 43-69] remains valid for the case of a hierarchical plane graph. We then prove that every internally triconnected clustered plane graph with a completely connected clustering structure admits a ''fully convex drawing,'' a planar straight-line drawing such that both clusters and facial cycles are drawn as convex polygons. We also present algorithms to construct such convex drawings of hierarchical graphs and clustered graphs.
---
paper_title: Convex drawings of graphs with non-convex boundary

paper_content:

In this paper, we study a new problem of finding a convex drawing of graphs with a non-convex boundary. It is proved that every triconnected plane graph whose boundary is fixed with a star-shaped polygon admits a drawing in which every inner facial cycle is drawn as a convex polygon. Such a drawing, called an inner-convex drawing, can be obtained in linear time.
---

Title: Survey on Convex Drawing of Planar Graph

Section 1: Introduction
Description 1: Introduce the problem of drawing planar graphs and the importance of convex drawing in recognizing graph structures.

Section 2: Literature Review
Description 2: Review the key contributions and findings in the field of convex drawing of planar graphs, including algorithms, conditions, and challenges.

Section 3: Prilimineries
Description 3: Define key concepts and terminologies related to planar graphs and their properties, such as cut vertices, biconnected and triconnected graphs.

Section 4: Description of Some Recent Works
Description 4: Provide details about recent advancements and specific linear time algorithms for convex drawings of planar graphs.

Section 5: Convex Drawing Algorithm
Description 5: Outline the steps of algorithms that use a convex polygon to generate convex drawings of planar graphs.

Section 6: Testing Algorithm
Description 6: Explain the testing algorithms that determine whether a given planar graph can be drawn convexly and the conditions required.

Section 7: Example
Description 7: Illustrate a computational example demonstrating the application of convex-testing and convex-drawing algorithms.

Section 8: Convex Drawing of Planar Graphs with Non-convex Boundary Constraints
Description 8: Discuss the challenges and solutions for convex drawing of planar graphs with non-convex boundary constraints.

Section 9: Convex Drawing with a Convex Boundary
Description 9: Describe conditions and algorithms for extending a convex polygon to a convex drawing of a plane graph.

Section 10: Convex Drawing with Star-Shaped Boundary Constraints
Description 10: Explore the concept of star-shaped boundaries and algorithms for extending convex drawings to include such boundaries.

Section 11: Convex Drawing with Crown-Shaped Boundary Constraints
Description 11: Discuss crown-shaped boundaries and the conditions for convex drawings of four-connected planar graphs with such boundaries.

Section 12: Convex Drawings of Hierarchical Planar Graphs
Description 12: Detail the results and algorithms for convex drawings of hierarchical planar graphs that have layering structures.

Section 13: Conclusion
Description 13: Summarize the different algorithms and variations for convex drawing of planar graphs and suggest future research directions.