China
Africa
Explore chapters and articles related to this topic
Tutte uniqueness and Tutte equivalence
Published in Joanna A. Ellis-Monaghan, Iain Moffatt, Handbook of the Tutte Polynomial and Related Topics, 2022
For a maximal simple outerplanar graph G, if, from the dual graph of G, we delete the vertex that corresponds to the outer face, we get the incidence graph τ(G) of the triangles in the embedding of G as a triangulation. Note that τ(G) is a tree with maximum degree at most three. We call τ(G) the dual tree of G (see Figure 6.6 for an example). Two maximal simple outerplanar graphs have isomorphic dual trees if and only if they are 2-isomorphic.
Crossing edge minimization in radial outerplanar layered graphs using segment paths
Published in Optimization Methods and Software, 2023
Francisco Madera-Ramírez, Joel Antonio Trejo-Sánchez, José López-Martínez, Jorge Ríos-Martínez
A straight-line drawing is a drawing in which every edge is mapped to a straight-line segment. An outerplanar graph is a planar graph that admits a planar drawing with all its vertices on the same (external) face; such a drawing is called an outerplanar drawing. If a graph can be drawn with no crossings using edges of arbitrary shape (e.g. polygonal lines or curves), then it can be drawn with no crossings using only straight-line edges [37]. A layered drawing of a graph is a drawing such that the vertices are constrained to lie on geometric layers that can be lines, circles, or other kinds of curves. Most of the literature assumes that the layers are either parallel straight lines (spine drawings) or concentric circles (radial drawings), which is also the most common requirement in real-world application domains [19].
A Pfaffian formula for matching polynomials of outerplanar graphs
Published in Optimization Methods and Software, 2021
An outerplanar graph is a graph that can be drawn on the plane without crossing edges so that all vertices are on the infinite face. Given a graph G, one can obtain a supergraph by adding a new vertex s and drawing edges from s to all the vertices in G. Then G is outerplanar if and only if is planar. Thus, one can check the outerplanarity of a given graph in linear time via planarity testing. The linear-time planarity testing algorithms [1,2], however, tend to require complicated procedures and/or sophisticated data structures. Sysło and Iri [9] instead described a direct method for testing outerplanarity in linear time.