Pathwidth of outerplanar graphs

We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin [3], after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a constant c such that the pathwidth of every biconnected outerplanar graph is at most c plus the pathwidth of its dual. They also conjectured that this was actually true with c being one for every biconnected planar graph. Fomin [10] proved that the second conjecture is true for all planar triangulations. First, we construct for each p ≥ 1, a biconnected outerplanar graph of pathwidth 2p + 1 whose (geometric) dual has pathwidth p + 1, thereby disproving both conjectures. Next, we also disprove two other conjectures (one of Bodlaender and Fomin [3], implied by one of Fomin [10]. Finally we prove, in an algorithmic way, that the pathwidth of every biconnected outerplanar graph is at most twice the pathwidth of its (geometric) dual minus one. A tight interval for the studied relation is therefore obtained, and we show that all cases in the interval happen. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 27–41, 2007     

A generalization of outerplanar graphs

Let G be a planar graph and W a set of vertices, G is W-outerplanar if it can be embedded in the plane so that all vertices of W lie on the exterior face. We give a characterization of these graphs by forbidden subgraphs, an upper bound on the number of edges, and other properties which lead to an algorithm of W-outerplanarity testing.     

The reconstruction of outerplanar graphs

Ulam's conjecture is that a graph G with at least three vertices can be reconstructed from the family of subgraphs of G obtained by deleting single vertices of G. This paper proves the conjecture for G outerplanar, by working first with partially labeled graphs and then applying the results obtained to the unlabeled case.     

Centers of maximal outerplanar graphs

The center of a graph is defined to be the subgraph induced by the set of vertices that have minimum eccentricities (i.e., minimum distance to the most distant vertices). It is shown that only seven graphs can be centers of maximal outerplanar graphs.     

On reconstructing maximal outerplanar graphs

Manvel has proved that a maximal outerplanar graph can be reconstructed from the collection of isomorphism types of subgraphs obtained by deleting vertices of the given graph. This paper sharpens Manvel's result by showing that if the graph is not a triangulation of a hexagon, then reconstruction can be accomplished using only those isomorphism types of subgraphs corresponding to deletion of vertices of valence two.     

Approximation of pathwidth of outerplanar graphs

There exists a polynomial time algorithm to compute the pathwidth of outerplanar graphs, but the large exponent makes this algorithm impractical. In this paper, we give an algorithm that, given a biconnected outerplanar graph G, finds a path decomposition of G of pathwidth at most twice the pathwidth of G plus one. To obtain the result, several relations between the pathwidth of a biconnected outerplanar graph and its dual are established.     

Game chromatic number of outerplanar graphs

This note proves that the game chromatic number of an outerplanar graph is at most 7. This improves the previous known upper bound of the game chromatic number of outerplanar graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 67–70, 1999     

外平面图的弱完备染色

假设G=（V,E,F）是一个平面图。如果e₁和e₂是G中两条相邻边且在关联的面的边界上连续出现,那么称e₁和e₂面相邻。图G的一个弱完备k-染色是指存在一个从V ∪ E ∪ F到k色集合{1, …, K}的映射,使得任意两个相邻点,两个相邻面,两条面相邻的边,以及V ∪ E ∪ F中任意两个相关联的元素都染不同的颜色。若图G有一个弱完备k-染色,则称G是弱完备k-可染的。平面图G的弱完备色数是指G是弱完备k-可染的正整数k的最小值,记成χ_vef（G）。2016年,Fabrici等人猜想：每个无环且无割边的连通平面图是弱完备7-可染的。证明外平面图满足猜想,即外平面图是弱完备7-可染的。     

Area-efficient planar straight-line drawings of outerplanar graphs

It is important to minimize the area of a drawing of a graph, so that the drawing can fit in a small drawing-space. It is well-known that a planar graph with n vertices admits a planar straight-line grid drawing with O(n²) area [H. de Fraysseix, J. Pach, R. Pollack, How to draw a planar graph on a grid, Combinatorica 10(1) (1990) 41-51; W. Schnyder, Embedding planar graphs on the grid, in: Proceedings of the First ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 138-148]. Unfortunately, there is a matching lower-bound of Ω(n²) on the area-requirements of the planar straight-line grid drawings of certain planar graphs. Hence, it is important to investigate important categories of planar graphs to determine if they admit planar straight-line grid drawings with o(n²) area.In this paper, we investigate an important category of planar graphs, namely, outerplanar graphs. We show that an outerplanar graph G with 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 manner in o(n²) area.     

On an interpolation property of outerplanar graphs

Let D be an acyclic orientation of a graph G. An arc of D is said to be dependent if its reversal creates a directed cycle. Let d(D) denote the number of dependent arcs in D. Define d_min(G) (d_max(G)) to be the minimum (maximum) number of d(D) over all acyclic orientations D of G. We determine d_min(G) for an outerplanar graph G and prove that G has an acyclic orientation with exactly k dependent arcs if d_min(G)?k?d_max(G).     

b-colouring outerplanar graphs with large girth

A b-colouring of a graph is a colouring of its vertices such that every colour class contains a vertex that has a neighbour in all other classes. The b-chromatic number of a graph is the largest integer $k$ such that the graph has a $b$-colouring with $k$ colours. We show here how to compute in polynomial time the $b$-chromatic number of an outerplanar graph of girth at least $8$. This generalizes the seminal result of Irving and Manlove on trees.     

Algebraic characterizations of outerplanar and planar graphs

A drawing of a graph in the plane is even if nonadjacent edges have an even number of intersections. Hanani’s theorem characterizes planar graphs as those graphs that have an even drawing. In this paper we present an algebraic characterization of graphs that have an even drawing. Together with Hanani’s theorem this yields an algebraic characterization of planar graphs. We will also present algebraic characterizations of subgraphs of paths, and of outerplanar graphs.     

On the chromatic index of outerplanar graphs

Vizing [Diskret. Analiz3 (1964), 25–30] has shown that if ? denotes the maximum valency of a simple graph, then its chromatic index is either ? or ? + 1. The object of this paper is to show that the chromatic index of an outerplanar graph G is ? if and only if G is not an odd circuit.     

Colouring games on outerplanar graphs and trees

Let f be a graph function which assigns to each graph H a non-negative integer f(H)≤|V(H)|. The f-game chromatic number of a graph G is defined through a two-person game. Let X be a set of colours. Two players, Alice and Bob, take turns colouring the vertices of G with colours from X. A partial colouring c of G is legal (with respect to graph function f) if for any subgraph H of G, the sum of the number of colours used in H and the number of uncoloured vertices of H is at least f(H). Both Alice and Bob must colour legally (i.e., the partial colouring produced needs to be legal). The game ends if either all the vertices are coloured or there are uncoloured vertices with no legal colour. In the former case, Alice wins the game. In the latter case, Bob wins the game. The f-game chromatic number of G, χ_g(f,G), is the least number of colours that the colour set X needs to contain so that Alice has a winning strategy. Let be the graph function defined as , for any n≥3 and otherwise. Then is called the acyclic game chromatic number of G. In this paper, we prove that any outerplanar graph G has acyclic game chromatic number at most 7. For any integer k, let ?_k be the graph function defined as ?_k(K₂)=2 and ?_k(P_k)=3 (P_k is the path on k vertices) and ?_k(H)=0 otherwise. This paper proves that if k≥8 then for any tree T, χ_g(?_k,T)≤9. On the other hand, if k≤6, then for any integer n, there is a tree T such that χ_g(?_k,T)≥n.     

Acyclic edge chromatic number of outerplanar graphs

A proper edge coloring of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by χ(G), is the least number of colors in an acyclic edge coloring of G. In this paper, we determine completely the acyclic edge chromatic number of outerplanar graphs. The proof is constructive and supplies a polynomial time algorithm to acyclically color the edges of any outerplanar graph G using χ(G) colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 22–36, 2010     

In-trees and plane embeddings of outerplanar graphs

A notion of anin-tree is introduced. It is then used to characterize and count plane embeddings of outerplanar graphs. In-trees have also been applied in the study of independent vertex covers of faces in outerplanar graphs.This research was partially supported by the grant RP.I.09, from the Institute of Informatics, University of Warsaw. Hospitality of the Institute of Datalogy, University of Copenhagen where this research has been completed is gratefully acknowledged.     

Proper orientation number of triangle-free bridgeless outerplanar graphs

An orientation of $G$ is a digraph obtained from $G$ by replacing each edge by exactly one of two possible arcs with the same endpoints. We call an orientation proper if neighboring vertices have different in-degrees. The proper orientation number of a graph $G$, denoted by $\overrightarrow{\chi }\left(G\right)$, is the minimum maximum in-degree of a proper orientation of $G$. Araujo et al asked whether there is a constant $c$ such that $\text{◂≤▸}\overrightarrow{\chi }\left(G\right)\le c$ for every outerplanar graph $G$ and showed that $\text{◂≤▸}\overrightarrow{\chi }\left(G\right)\le 7$ for every cactus $G$. We prove that $\text{◂≤▸}\overrightarrow{\chi }\left(G\right)\le 3$ if $G$ is a triangle-free 2-connected outerplanar graph and $\text{◂≤▸}\overrightarrow{\chi }\left(G\right)\le 4$ if $G$ is a triangle-free bridgeless outerplanar graph.