Stavros D Nikolopoulos
email: stavros@cs.uoi.gr

Leonidas Palios
email: palios@cs.uoi.gr

On the Recognition of Bipolarizable and P 4 -simplicial Graphs

Keywords: Bipolarizable (Raspail) graphs, P4-simplicial graphs, perfectly orderable graphs, recognition, algorithms, complexity

. In this paper, we consider the recognition problem on these classes of graphs and present algorithms that solve it in O(nm) time. In particular, we prove properties of the graphs investigated and show that we can produce bipolarizable and P4simplicial orderings on the vertices of the input graph G, if such orderings exist, working only on P3s that participate in a P4 of G. The proposed recognition algorithms are simple, use simple data structures and both require O(n + m) space. Additionally, we show how our recognition algorithms can be augmented to provide certificates, whenever they decide that G is not bipolarizable or P4-simplicial; the augmentation takes O(n + m) time and space. Finally, we include a diagram on class inclusions and the currently best recognition time complexities for a number of perfectly orderable classes of graphs.

Introduction

A linear order ≺ on the vertices of a graph G is perfect if the ordered graph (G, ≺) contains no induced P 4 abcd with a ≺ b and d ≺ c (such a P 4 is called an obstruction). In the early 1980s, Chvátal [START_REF]Perfectly ordered graphs[END_REF] defined the class of graphs that admit a perfect order and called them perfectly orderable graphs.

Chvátal proved that if a graph G admits a perfect order ≺, then the greedy coloring algorithm applied to (G, ≺) produces an optimal coloring using only ω(G) colors, where ω(G) is the clique number of G. This implies that the perfectly orderable graphs are perfect; a graph G is perfect if for each induced subgraph H of G, the chromatic number χ(H) equals the clique number ω(H) of the subgraph H. The class of perfect graphs was introduced in the early 1960s by Berge [START_REF] Berge | Färbung von Graphen deren sämtliche bzw. deren ungerade Kreise starr (Zusammenfassung)[END_REF], who also conjectured that a graph is perfect if and only if it contains no induced subgraph isomorphic to an odd cycle of length at least five, or to the complement of such an odd cycle. This conjecture, known as the strong perfect graph conjecture, has been recently established due to the work of Chudnovsky et al. [START_REF] Chudnovsky | The strong perfect graph theorem[END_REF].

It is well-known that several interesting problems in graph theory (e.g., coloring, independent set), which are NP-complete in general graphs, have polynomial-time solutions in graphs that admit a perfect order [2; 8]; unfortunately, it is NP-complete to decide whether a graph admits a perfect order [START_REF] Middendorf | On the complexity of recognizing perfectly orderable graphs[END_REF]. Since the recognition of perfectly orderable graphs is NP-complete, we are interested in characterizing graphs which form polynomially recognizable subclasses of perfectly orderable graphs. Many such classes of graphs, with very interesting structural and algorithmic properties, have been defined so far and shown to admit polynomial-time recognitions (see [2; 8]); note however that not all subclasses of perfectly orderable graphs admit polynomial-time recognitions [START_REF] Hoàng | On the complexity of recognizing a class of perfectly orderable graphs[END_REF].

In 1989, Hoàng and Reed [START_REF] Hoàng | Some classes of perfectly orderable graphs[END_REF] introduced four subclasses of perfectly orderable graphs, namely, the P 4 -indifference, Raspail (also known as Bipolarizable), P 4 -simplicial, and P 4 -comparability graphs; a graph is defined to be • P 4 -indifference if it admits a linear order ≺ on its vertices such that every P • Bipolarizable if it admits a linear order ≺ on its vertices such that every P 4 abcd has (b ≺ a, c ≺ d);

• P 4 -simplicial if it admits a linear order ≺ such that every P 4 has either a bipolarizable or a P 4indifference ordering;

• P 4 -comparability if it admits a linear order ≺ on its vertices such that every P Hoàng and Reed proved structural and algorithmic properties for these four classes of perfectly orderable graphs, and provided polynomial-time recognition algorithms and also polynomial-time algorithms for constructing obstruction-free linear orders (i.e., perfect orderings). Note that every linear order ≺ on the vertices of a graph yields an acyclic orientation of the edges, where each edge ab is oriented from a to b if and only if a ≺ b; thus, a graph is bipolarizable if we can assign orientations to its edges so that the wings of every P 4 are oriented towards the endpoints of the P 4 . On the other hand, every acyclic orientation gives at least one linear order; for example, the order taken by a topological sorting. Hence, bipolarizable and P 4 -simplicial graphs can also be defined in terms of orientations. Additionally, the class of bipolarizable graphs can be defined in terms of forbidden subgraphs. The minimal set of forbidden subgraphs for this class has been established in [12; 16]; it includes the graphs shown in Figure 1 (we will call the rightmost among them zig-zag triomino or z-triomino for short) and the k-wheel (k ≥ 3) defined as follows (nearly following the notation of [START_REF] Hertz | Bipolarizable graphs[END_REF]): a k-wheel (k ≥ 3) is the graph formed by a set of 3k vertices, namely, v 0 , v 1 , . . ., v k-1 , r 0 , r 1 , . . ., r k-1 , and s 0 , s 1 , . . ., s k-1 , such that ⊲ the vertices v 0 , v 1 , . . . , v k-1 form a clique, while each of the vertex sets {r 0 , r 1 , . . . , r k-1 } and {s 0 , s 1 , . . . , s k-1 } is an independent set, ⊲ for 0 ≤ i, j ≤ k -1, v i is adjacent to r j except for j = i + 1,

⊲ for 0 ≤ i, j ≤ k -1, v i is adjacent to s j except for j = i, i + 1, and
⊲ for 0 ≤ i ≤ k -1, r i is adjacent to s i but non-adjacent to any s j for j = i,
where all integer subscripts are taken modulo k. We note that the 2-wheel is also well defined and coincides with P 6 . A figure depicting the k-wheels for k = 2, 3, 4, 6 can be found in [START_REF] Hertz | Bipolarizable graphs[END_REF]. Unlike the bipolarizable graphs, the minimal set of forbidden subgraphs for the class of P 4 -simplicial graphs, if it can be concisely described, has not been determined. Another interesting class of graphs is the class of weak bipolarizable graphs: a graph is weak bipolarizable if it has no induced subgraph isomorphic to C k for k ≥ 5, to the house graph (P 5 ), or to the graphs A and D 6 of Figure 1. The class was introduced by Olariu [START_REF] Olariu | Weak bipolarizable graphs[END_REF] who also presented an O(n 3 )-time recognition algorithm. Since any C k , where k ≥ 7, contains a P 6 , the class of weak bipolarizable graphs is a superclass of the bipolarizable graphs, as the name suggests after all (see also [START_REF] Olariu | Weak bipolarizable graphs[END_REF]).

As mentioned above, the recognition problem on both bipolarizable and P 4 -simplicial graphs has been addressed by Hoàng and Reed [START_REF] Hoàng | Some classes of perfectly orderable graphs[END_REF]. Their algorithms are based on detecting whether the input graph G admits a bipolarizable or P 4 -simplicial ordering. More precisely, the algorithm for recognizing a bipolarizable graph G constructs an acyclic bipolarizable orientation; for every P 4 abcd in G, it orients ab (resp. cd) towards a (resp. d); if no edge of G receives opposite orientations and the resulting oriented graph is acyclic, it returns "yes", otherwise returns "no". The algorithm runs in O(n 4 ) time, where n is the number of vertices of the input graph G. Their algorithm for recognizing P 4 -simplicial graphs constructs a P 4 -simplicial ordering of the vertices of G as follows: it initially sets H := V (G) and then repeatedly chooses a vertex x ∈ H such that x is not a midpoint of any P 4 abxc (of the graph G) with b, c ∈ H and sets H := H -{x} and y ≺ x for all y ∈ H; if H = ∅ and the algorithm fails to choose a vertex x ∈ H, it returns "no". This algorithm takes O(n 5 ) time.

Recently, Eschen et al. [START_REF] Eschen | Recognition of some perfectly orderable graph classes[END_REF] described recognition algorithms for several classes of perfectly orderable graphs, e.g., O(n 3.376 )-time algorithms for both bipolarizable and P 4 -simplicial graphs. In particular, they presented an algorithm for recognizing brittle graphs by direct application of the definition; a graph is brittle if and only if its vertices admit a linear order (v 1 , v 2 , . . . , v n ) such that each vertex v i is either not a midpoint or not an endpoint of a P 4 in the subgraph of G induced by {v i , . . . , v n } [2; 14]. Their algorithm uses matrix multiplication and runs in O(n 3.376 ) time; it computes, for each vertex v i , the P 4 s which contain v i as a midpoint, and thus, is also used to recognize bipolarizable and P 4 -simplicial graphs within the same time bounds.

Additionally, we note that Hoàng and Reed also presented algorithms which solve the recognition problem for P 4 -comparability and P 4 -indifference graphs which run in O(n 4 ) and O(n 6 ) time [16; 17]. Recent results on these problems include O(nm)-time [START_REF] Nikolopoulos | Algorithms for P 4 -comparability graph recognition and acyclic P 4 -transitive orientation[END_REF] and O(n + m)-time algorithms [10; 26], respectively, where m is the number of edges of the input graph.

Our objective is to study the recognition problem on the classes of bipolarizable and P 4 -simplicial graphs and we present O(nm)-time algorithms for each of these problems. Our algorithms rely on properties of these graphs which we establish and which allow us to only work with P 3 s of the input graph G which participate in P 4 s of G; such P 3 s can be computed in O(nm) time by means of the distance trees of the complement of the graph rooted at each of its vertices [START_REF] Nikolopoulos | Algorithms for P 4 -comparability graph recognition and acyclic P 4 -transitive orientation[END_REF]. The proposed recognition algorithms are simple, use simple data structures and both require O(n + m) space. Additionally, we describe how to augment our two recognition algorithms so that they return a certificate whenever they decide that G is not bipolarizable or P 4 -simplicial, thus, providing the most natural evidence that the input graph G indeed is not bipolarizable or P 4 -simplicial. In particular, for the case of bipolarizable graphs, the augmented algorithm returns a forbidden subgraph contained in G. The augmented algorithms take O(n + m) additional time and O(n + m) space. Finally, we show that the class of weak bipolarizable graphs is a subclass of the class of P 4 -simplicial graphs and give class inclusion results and the currently best time complexities for the recognition problem for a number of perfectly orderable classes of graphs.

The paper is structured as follows. In Section 2 we review the terminology that we use throughout the paper and we establish the theoretical framework on which our algorithms are based. The recognition algorithms for bipolarizable and P 4 -simplicial graphs are described and analyzed in Sections 3 and 4, respectively. Section 5 gives results on class inclusions for a number of perfectly orderable classes, and Section 6 concludes with a summary of our results and some open problems.

Theoretical Framework

We consider finite undirected graphs with no loops or multiple edges. Let G be such a graph; then, V (G) and E(G) denote the set of vertices and of edges of G respectively. The neighborhood N (x) of a vertex x ∈ V (G) is the set of all the vertices of G which are adjacent to x. The closed neighborhood of x is defined as

N [x] := {x} ∪ N (x).
The subgraph of G induced by a subset S of G's vertices is denoted by G

[S]. A subset A ⊆ V (G) of p vertices is a p-clique, or clique, if it induces a complete subgraph, i.e., G[A] = K p ; a single vertex is a 1-clique. An independent set is a subset B ⊆ V (G) of vertices no two of which are adjacent; it is also called stable set. A subset H ⊆ V (G) of vertices is homogeneous if 2 ≤ |H| < |V (G)| and each vertex x ∈ V (G) -H sees either all vertices or no vertex in H, i.e., either H ⊆ N (x) or H ∩ N (x) = ∅. A path in a graph G is a sequence of vertices v 0 v 1 • • • v k such that v i-1 v i ∈ E(G) for i = 1, 2
, . . . , k; we say that this is a path from v 0 to v k and that its length is k. A path may be undirected or directed depending on whether G is an undirected or directed graph. A path is called simple if none of its vertices occurs more than once; it is called trivial if its length is equal to 0. A path (simple path)

v 0 v 1 • • • v k is called a cycle (simple cycle) of length k + 1 if v 0 v k ∈ E(G).
An edge connecting two non-consecutive vertices in a simple path (cycle) is called a chord; then, a simple path (cycle

) v 0 v 1 • • • v k of a graph G is chordless if G contains no chords of the path (cycle), i.e., v i v j /
∈ E(G) for any two non-consecutive vertices v i , v j in the path (cycle). The chordless path (chordless cycle, respectively) on n vertices is commonly denoted by P n (C n , respectively). In particular, a chordless path on 4 vertices is denoted by P 4 .

Let abcd be an induced P 4 of a graph. The vertices b and c are called midpoints and the vertices a and d endpoints of the P 4 abcd. The edge connecting the midpoints of a P 4 is called the rib; the other two edges (which contain some endpoint) are called the wings. For the P 4 abcd, the edge bc is its rib and the edges ab and cd are its wings.

Our bipolarizable graph recognition algorithm relies on the result stated in the following lemma.

Lemma 2.1 Let G be a graph that contains no induced subgraph isomorphic to a house graph or the graphs A and D 6 of Figure 1. Then, G does not contain a C 4 abcd such that abc and bcd are P 3 s participating in P 4 s of G.

Proof: Suppose for contradiction that G contains a C 4 abcd meeting the conditions in the statement of the lemma. We distinguish cases. Suppose first that the P 3 abc participates in the P 4 abcx and that the P 3 bcd participates in the P 4 bcdy. Then, xd / ∈ E(G), otherwise the vertices a, b, c, d, x would induce a house in G. In a similar fashion, ya / ∈ E(G) either. But then, if xy / ∈ E(G), then the subgraph induced by a, b, c, d, x, y is isomorphic to the A whereas if xy ∈ E(G), it is isomorphic to the D 6 ; a contradiction in either case. The remaining three cases (depending on whether abc participates in a P 4 xabc or abcx and on whether bcd participates in a P 4 ybcd or bcdy) are handled similarly. ✷

We note that Lemma 2.1, as well as the ensuing Lemma 3.1, in fact hold for the class of weak bipolarizable graphs, which is a superclass of the bipolarizable graphs. Lemma 2.1 however holds neither for the class of P 4 -simplicial graphs nor for the class of HHD-free graphs [2; 18; 24], since the former class contains the house graph whereas the latter contains the graph A.

Computing all the P 3 s participating in P 4 s of a graph G: In [START_REF] Nikolopoulos | Algorithms for P 4 -comparability graph recognition and acyclic P 4 -transitive orientation[END_REF], it has been shown that all the P 3 s participating in P 4 s of a graph G can be efficiently computed as follows:

Lemma 2.2 For each vertex v of a graph G, let T G (v) be the distance tree of the complement of G rooted at v (0-th level) and let S 1 , S 2 , . . . , S kv be a partition of the vertices in the 2nd level of the tree, where two vertices belong to the same S i iff they have the same neighbors in the 1st level of T G (v). Then, avb is a P 3 participating in a P 4 of G iff ab / ∈ E(G) and either exactly one of a, b belongs to the 2nd level and the other to the 3rd level of T G (v), or both a and b belong to the 2nd level but they are in different sets of the partition S 1 , S 2 , . . . , S kv . Lemma 2.2 implies that for a graph G on n vertices and m edges, the P 3 s participating in P 4 s of G can be computed in O(nm) time and O(n + m) space because the number of vertices in all the levels, but the 0th and the 1st, of the distance tree T G (v) does not exceed the degree of v in G; thus, considering pairs of vertices located in these levels takes O( v deg 2 (v)) = O(nm) time, where deg(v) denotes the degree of v in the graph G [START_REF] Nikolopoulos | Algorithms for P 4 -comparability graph recognition and acyclic P 4 -transitive orientation[END_REF].

Since the vertices in the 2nd and 3rd level of T G (v) form a subset of the neighborhood of v, we can give a more unified criterion for deciding whether a P 3 avb participates in a P 4 of G by considering the following partition of N (v):

⊲ the partition of the vertices in the 2nd level of T G (v) into S 1 , . . . , S kv as described above; ⊲ all the vertices in the 3rd level of T G (v) are placed in a set S kv+1 ; ⊲ all remaining vertices in N (v) are placed in a set S 0 (no such vertex a forms a P 3 avb participating in P 4 s of G for any vertex b of G).

Then, Lemma 2.2 can be equivalently stated as follows:

Lemma 2.3 For each vertex v of a graph G, let T G (v)
be as in Lemma 2.2 and let S 0 , S 1 , . . . , S kv , S kv+1 be the partition described above. Then, for any a, b ∈ N (v) such that a ∈ S i and b ∈ S j , avb is a P 3 participating in a P 4 of G if and only if ab / ∈ E(G), i = 0, j = 0, and i = j.

Recognition of Bipolarizable Graphs

The definition of bipolarizable graphs implies that they can be efficiently recognized as soon as the wings of all the P 4 s have been computed. The method described in [START_REF] Nikolopoulos | Algorithms for P 4 -comparability graph recognition and acyclic P 4 -transitive orientation[END_REF] for computing all the P 3 s participating in P 4 s of a given graph does not seem to extend to produce within the same time complexity which edge of the P 3 is the rib and which is the wing of the P 4 . However, in the case of bipolarizable graphs, we take advantage of Lemma 2.1 in order to achieve their efficient recognition. Indeed, since the bipolarizable graphs do not contain the house graph, A, or D 6 (see Figure 1), Lemma 2.1 implies the following result.

Lemma 3.1 Let G be a bipolarizable graph and let abc be a P 3 participating in a P 4 of G. If bcd is another such P 3 , then G contains the P 4 abcd.

Proof: If the path abcd is not a P 4 then G must contain the edge ad. But this creates a C 4 meeting the conditions of Lemma 2.1; a contradiction. ✷

Then, Lemma 3.1 implies the following corollary.

Corollary 3.1 Let G be a bipolarizable graph and let F be the orientation of G such that the wings of each P 4 of G are oriented towards the endpoints of the P 4 and edges that are not the wings of any P 4 are not oriented. Then, for each edge bc of G for which there exist P 3 s abc and bcd participating in P 4 s of G, the edges ab and cd (for all such a and d) get oriented towards a and d respectively.

Proof: Let us consider any such P 3 abc; then, because of the existence of the P 3 bcd, Lemma 3.1 applies, and thus abcd is a P 4 of G. Therefore, the edge ab is oriented towards a in F , and this holds for all such a, and the edge cd is oriented towards d in F and this holds for all such d. ✷

The algorithm for the recognition of bipolarizable graphs applies Corollary 3.

Bipolarizable Graph Recognition Algorithm

Input:

an undirected graph G on n vertices and m edges. Output: a message as to whether G is a bipolarizable graph or not. The correctness of the algorithm follows directly from Corollary 3.1. Observe that for any P 4 abcd of G, the edge bc will be considered in Step 3 of the algorithm, and then the edges ab and cd will be assigned the desired orientations.

Time and Space Complexity.

Step 1 takes O(n + m) time since the sorted adjacency lists can be obtained through radix sorting an array of all the ordered pairs of adjacent vertices, while Step 2 takes O(nm) time [START_REF] Nikolopoulos | Algorithms for P 4 -comparability graph recognition and acyclic P 4 -transitive orientation[END_REF]. Steps 3b and 3c take constant time per such vertex w; it is assumed that the orientation of an edge is stored in an array of size m for constant-time access and update. For an edge uv, Steps 3b and 3c may be executed as many as Θ(deg(u) + deg(v)) times, where deg(u) denotes the degree of vertex u in G. Since Step 3a also takes O(deg(u)

+ deg(v)) time, Step 3 takes O(nm) time because uv∈E(G) (deg(u)+deg(v)) = uv∈E(G) deg(u) + uv∈E(G) deg(v) = u∈V (G) deg(u)•deg(u) = O(nm).
Step 4 can be executed by constructing the directed graph -→ G and then by applying topological sorting on it; if the topological sorting succeeds then no directed cycle exists, otherwise there exists a directed cycle. From this description, it is clear that Step 4 can be completed in O(n + m) time and space. Since the computation of the P 3 s participating in P 4 s takes linear space, the total space needed by the recognition algorithm is clearly linear in the size of the input graph G.

Summarizing, we obtain the following theorem. The recognition algorithm can be used to produce a bipolarizable ordering of the vertices of a bipolarizable graph G. The bipolarizable ordering coincides with the topological ordering of the vertices of the directed graph -→ G , possibly extended by an arbitrary ordering of any vertices of G which do not participate in -→ G .

Providing a Certificate

The bipolarizable graph recognition algorithm can be easily augmented so that it provides a certificate whenever it decides that the input graph G is not bipolarizable; in particular, the algorithm can be made to return a forbidden subgraph of G in such a case. As indicated by the algorithm, there are two reasons due to which a given graph G can be found nonbipolarizable. First, a conflict of orientation may arise on an edge of G which ends up receiving opposite orientations by different P 4 s sharing it. Second, if no conflict has arisen, there may be the case that the directed subgraph -→ G spanned by the oriented edges contains a directed cycle. Relating these two cases to the forbidden subgraphs, it is not difficult to see that: Lemma 3.2 A conflict of orientation arises while orienting the edges of a graph G if and only if G contains a C 5 , a house graph, a P 6 , an A, a C 6 , or a D 6 (see Figure 1).

Proof: It is easy to see that if the graph G contains any of the above graphs then a conflict of orientation arises; the bottom horizontal edge of the C 5 and the house, and the top horizontal edge of P 6 , A, C 6 , D 6 in Figure 1 In the following, we will consider graphs that contain no C 5 , house, P 6 , A, C 6 , or D 6 . Then, by Lemma 3.2, the wings of every P 4 of G can all be oriented without conflict towards the endpoints of the P 4 . The orientation process produces directed and undirected edges; we say that an edge xy is not oriented towards x, if it is either undirected or directed towards y. The following lemma will be useful later.

Lemma 3.3 Let G be a graph which contains no C 5 , house, P 6 , A, C 6 , or D 6 , and whose edges have been oriented as described above. Suppose further that G contains a cycle bcf g with a single diagonal bf such that the edge f g is oriented towards f , the edge bg is not oriented towards b, the edge cf is not oriented towards f , and the diagonal bf is undirected. Then, if ahgf is any P 4 of G, the vertices a, b, c, f, g, h induce in G a subgraph as the one shown on the right in Figure 2 and the edge cf is oriented towards c.

Proof:

The cycle bcf g is shown on the left in Figure 2; white arrows indicate potential orientations. It is easy to see that vertex b is adjacent to both a and h in G: if b was adjacent neither to a nor to h, the path ahgb would be a P 4 with its wing bg oriented away from the endpoint b, in contradiction to the potential orientation of bg; if b was adjacent to a but not to h, the vertices a, b, f, g, h would induce a house in G; if b was adjacent to h but not to a, the path ahbf would be a P for otherwise the path ahcf would be a P 4 with its wing cf oriented towards f , in contradiction to the potential orientation of cf . The above adjacencies imply that the path cf gh is a P 4 and thus the edges cf and gh are oriented towards c and h respectively. ✷ Using Lemma 3.3 we prove the following lemma which is important for locating z-triominoes. Proof: (=⇒) Suppose that G contains a z-triomino. Since G contains no C 5 , house, P 6 , A, C 6 , or D 6 , each edge of G will receive at most one orientation (Lemma 3.2). Thus, the edges of each z-triomino of G receive the orientations indicated in Figure 3; that is, for the z-triomino with vertices a, b, c, d, e, f, g, h, a single directed cycle bcf g is formed. It suffices to show that the diagonal bf is not the wing of any P 4 of G and thus receives no orientation. Clearly, it does not get oriented due to a P 4 induced by a subset of the vertices of the z-triomino. Due to symmetry, considering P 4 s with vertices in addition to the vertices of the triomino is exhausted to the following three cases (see Figure 3): This in turn implies that xc ∈ E(G), otherwise the path xycf would be a P 4 whose wing f c would be oriented towards c. The existence of xc implies the existence of xg and the non-existence of xh since otherwise the paths gf cx and f cxh would be "badly" oriented P 4 s respectively. But then, the subgraph induced by the vertices b, c, x, g, h is a house; a contradiction.

A contradiction has been obtained in each case, which implies that the edge bf is not the wing of any P 4 of the graph G and thus it does not receive an orientation.

(⇐=) Now suppose that the directed graph -→ G exhibits a directed cycle bgf c with a single undirected diagonal bf . Lemma 3.3 applies for this cycle in terms of the edge f g and any P 4 ahgf of G. Lemma 3.3 also applies for the same cycle in terms of the edge bc and any P 4 bcde of G; it is important to observe that the vertices a, h differ from d, e as they have different neighbors among b, c, f, g. As a result, the vertices a, b, c, d, e, f, g, h induce a subgraph containing the edges of the z-triomino shown in Figure 3 and potentially edges connecting a, h to d, e. In fact, d and h are not adjacent, otherwise the path cdhg would be a P 4 whose wing cd would be oriented away from the endpoint c. This implies that neither e, h nor a, d are adjacent, otherwise, there would exist P 4 s cdeh and dahg, respectively, with their wings cd and gh oriented away from the endpoint. Finally, a, e are not adjacent either; if they were adjacent, the path haed would be a P 4 whose wing ah would be oriented away from the endpoint h. The above adjacencies imply that the vertices a, b, c, d, e, f, g, h induce a z-triomino in G.

✷

Additionally, we give below a result of Hertz ([12], Lemma 2.4) which we have paraphrased using our formalism and terminology:

Lemma 3.5 Let C = v k-1 v k-2 • • • v 1 v 0 be a directed cycle on k ≥ 3 vertices without any directed chord. Let us consider the directed path v n-1 v n-2 • • • v 0 on n ≤ k consecutive vertices of C. Let r i , s i (1 ≤ i ≤ n -1)
be any vertices such that the paths s i r i v i v i-1 are P 4 s of G. Then, the vertices v 0 , v 1 , . . . , v n-1 , r 1 , r 2 , . . . , r n-1 , and s 1 , s 2 , . . . , s n-1 induce a quasi n-wheel in G.

(We note that in Lemma 3.5 it is implied that no conflict of orientation has arisen and that the graph G contains all chords connecting the k vertices of the directed cycle C.) A quasi k-wheel is what remains from a k-wheel with vertex set {v 0 , v 1 , . . . , v n-1 , r 0 , r 1 , . . . , r n-1 , s 0 , s 1 , . . . , s n-1 } when vertices r 0 and s 0 are removed. Hertz used Lemma 3.5 to establish his main theorem; in the proof, he shows the following:

Lemma 3.6 Let C = v n-1 v n-2 • • • v 1 v 0 be
a directed cycle on n ≥ 3 vertices without any directed chord. Let r i , s i (0 ≤ i ≤ n -1) be any vertices such that the paths s i r i v i v i-1 are P 4 s of G. Then, the vertices v 0 , v 1 , . . . , v n-1 , r 0 , r 1 , . . . , r n-1 , and s 0 , s 1 , . . . , s n-1 induce an n-wheel in G.

Finally, we can also show the following results. Lemma 3.7 Let G be a graph which contains no C 5 , house, P 6 , A, C 6 , or D 6 , and whose edges have been oriented as described earlier yielding the directed graph -→ G . Then:

(i) G does not contain a C 4 bcf g such that the edge f g is oriented towards f , the edge bc is not oriented towards c, and the edge cf is not oriented towards f .

(ii) If -→ G contains a directed C k where k ≥ 5 (i.

e., there are no directed chords), the vertices of the cycle induce a complete graph in G.

Proof: (i) Suppose for contradiction that the graph G contains such a C 4 . The orientation of the edge f g implies that G contains an induced P 4 , say, ahgf , with wing f g. Then, as in the proof of Lemma 3.3, we can show that c is adjacent neither to a nor to h. If ac ∈ E(G), then G would contain a house or a C 5 depending on whether c, h are adjacent or not. Since a, c are not adjacent then c, h are not adjacent either, otherwise the path ahcf would be a P 4 whose wing cf would be oriented towards f , in contradiction to the potential orientation of cf given in the statement of the lemma. the path cbgh would be a P 4 whose wing cb would be oriented towards c, again in contradiction to the potential orientation of bc. But then, the vertices b, c, f, g, h induce a house in G; a contradiction. (ii) Suppose for contradiction that the directed graph -→ G contains a directed C k on k ≥ 5 vertices and two of them are not adjacent in G; without loss of generality, we assume that the

C k is v 0 v 1 • • • v k-1 (oriented from v 0 to v 1 and so on to v k-1 and back to v 0 ) and that v 0 v t / ∈ E(G) where 1 < t < k -2. Let q = max 0≤i<t { i | v i v t / ∈ E(G) and v i+1 v t ∈ E(G)};
we note that q is well defined since v 0 v t / ∈ E(G) and v t-1 v t ∈ E(G). Next, we show that there exist vertices v p , v r such that the vertices v p , v q , v q+1 , v r appear in that order around the directed C k of the graph -→ G and induce in G the cycle v p v q v q+1 v r where v p v q+1 ∈ E(G) and v q v r / ∈ E(G); see Figure 4(a). We consider a chordless path ρ connecting

v t to v q in the sub- graph G[{v t , v t+1 , . . . , v k-1 , v 0 , v 1 , . . . , v q }]; let us suppose that ρ = v t v i1 v i2 • • • v i ℓ v q , where ℓ ≥ 1 since v q v t / ∈ E(G). If ℓ = 1 then we have the cycle v q v q+1 v t v i1 where v q v t / ∈ E(G). If v i1 v q+1 / ∈ E(G) then the cycle v q v q+1 v t v i1
meets the conditions of statement (i) of this lemma for b = v i1 , c = v t , f = v q+1 , and g = v q (note that the edges v q+1 v t , v t v i1 , and v i1 v q are either chords or they are directed towards v t , v i1 , and v q , respectively); since this is impossible according to statement (i), we conclude that v i1 v q+1 ∈ E(G). Then, we have the desired cycle for v p = v i1 and v r = v t . Suppose now that ℓ ≥ 2. Let us consider that v i0 = v t and let s = max 0≤j≤ℓ { j | v ij v q+1 ∈ E(G) }; s is well defined since the edge v i0 v q+1 = v t v q+1 belongs to E(G). Since G contains no C 5 , C 6 , or P 6 , and effectively no C i for i ≥ 5, it follows that s ≥ ℓ -1. But s = ℓ -1, otherwise the cycle v q v q+1 v i ℓ-1 v i ℓ would meet the conditions of statement (i) of this lemma for b = v i ℓ , c = v i ℓ-1 , f = v q+1 , and g = v q , and that would be impossible; recall that the path ρ is chordless. Thus, s = i ℓ . Then, v q+1 v i ℓ-1 ∈ E(G); if not, then depending on whether v q+1 v i ℓ-2 ∈ E(G) or not, G would contain either a house or a C i for i ≥ 5, respectively. Therefore, we have the desired cycle for

v p = v i ℓ and v r = v i ℓ-1 .
The existence of a cycle 4(a)); in turn, the lemma implies (i) that for any P 4 ahv q v q+1 of G, the vertices a, v p , v r , v q+1 , v q , h induce a subgraph isomorphic to the one shown on the right in Figure 2, and (ii) that the edge v q+1 v r is oriented towards v r .

v p v q v q+1 v r such that v p v q+1 ∈ E(G) and v q v r / ∈ E(G) implies that we can find v p , v r such that v p ∈ {v r+1 , v r+2 , . . . , v k-1 , v 0 , . . . , v q-1 } and the length of the path v r v r+1 • • • v p is minimized. The properties of the cycle v p v q v q+1 v r imply that Lemma 3.3 applies on it for b = v p , c = v r , f = v q+1 , and g = v q (Figure
The latter fact implies that v r = v q+2 , since among all the edges of G connecting vertices of the cycle v 0 v 1 • • • v k only the edges of the cycle are directed (Figure 4(b)). We distinguish the following cases: a. v p = v q+3 : In this case, the edge v q+2 v p is directed towards v p and then Lemma 3.3 applies on the cycle v p v q v q+1 v q+2 for b = v q+1 , c = v q , f = v p , and g = v r , implying that the edge v p v q is oriented towards v q ; however, this contradicts the fact that the cycle

v 0 v 1 • • • v k-1 is of length k ≥ 5 with no directed chords. b. v q+1 v q+3 / ∈ E(G):
Then, the orientations of the edges v q v q+1 , v q+1 v q+2 , and v q+2 v q+3 imply that v q v q+3 ∈ E(G), i.e., the vertices v q , v q+1 , v q+2 , v q+3 induce a C 4 in G; this leads to a contradiction as well since Lemma 3.7 (statement (i)) applies on this C 4 .

c. v p = v q+3 and v q+1 v q+3 ∈ E(G): Then, v q v q+3 / ∈ E(G) for otherwise G would contain the cycle v q v q+1 v q+2 v q+3 , contradicting the minimality of the choice of v p , v r . Since v q v q+3 / ∈ E(G), then for the same reason, v p v q+3 /
∈ E(G); otherwise, G would contain the cycle v p v q v q+1 v q+3 . Thus, the situation is as shown in Figure 4(c) where v q+3 may also be adjacent to a, h in G. Since the chord v q+1 v q+3 is undirected, the path av p v q+1 v q+3 is not a P 4 , and thus av q+3 ∈ E(G). But then, the vertices a, h, v q , v q+1 , v q+3 induce either a house or a C 5 depending on whether h, v q+3 are adjacent in G or not, a contradiction.

We reached a contradiction in each case, and thus the directed graph -→ G cannot contain a directed C k , where k ≥ 5, such that the vertices of the cycle do not induce a complete graph in G. ✷

The above lemmata suggest the following additions to our bipolarizable graph recognition algorithm so that a forbidden subgraph is returned whenever the input graph G is deemed non-bipolarizable: The correctness of Steps A.1 and A.2 follows from Lemma 3.2 and its proof, while the correctness of Steps B.1 and B.2 follows from Lemmata 3.4, 3.6, and 3.7. In the following, we describe in detail, the components required to efficiently carry out the above computations.

3.1.1 Locating a P 4 abcd when given an edge ab.

We assume that with each edge of G, we store pointers to the vertex records of its endpoints; thus, from the edge ab, we can access a and b in constant time. Then, we find the sought P 4 abcd as follows:

1. store the neighbors of the vertices a and b in an array each for constant time adjacency tests;

2. for each edge uw of G do if u is adjacent to b but not to a and w is adjacent neither to a nor to b then the sought P 4 is the path abuw; return; if u is adjacent neither to a nor to b and w is adjacent to b but not to a then the sought P 4 is the path abwu; return;

The correctness of the computation is a direct consequence of the adjacencies of the vertices a, b, u, w.

Locating a directed cycle without directed chords.

To locate a directed cycle in the directed subgraph -→ G spanned by the oriented edges of G, we apply depth-first search on -→ G and obtain an ordered list L of the vertices of such a cycle. Then, in order to isolate a directed cycle with no directed chords, we use the following procedure get c-d-cycle(L) on L. The procedure clips portions of the list L until it obtains a directed cycle without any directed chords, as desired. We assume that each record in the list is initially associated with its rank in the list L. These integers will not be updated, and, due to clipping, they will not match the current ranks; nevertheless, they will reflect the order of the vertex records along the directed cycle stored in L at any given time.

get c-d-cycle(L)

for each vertex x in order in the list L do find the vertex y, if any, such that the edge xy is directed towards x, and y exhibits the smallest "rank" larger than x's; if no such vertex y exists then find the vertex z, if any, such that the edge xz is directed towards z, and z exhibits the largest "rank" larger than x's; if such a vertex z exists then clip the list L by removing any vertex records between x and z; else find the vertex z, if any, such that the edge xz is directed towards z, and z exhibits the largest "rank" larger than x's and smaller than y's; if no such vertex z exists then clip the list L by removing any vertex records to the left of x and to the right of y; else clip the list L by maintaining the vertex record for x followed by those between z and y inclusive; 4 Recognition of P 4 -simplicial Graphs

Our P 4 -simplicial graph recognition algorithm relies on the corresponding algorithm of Hoàng and Reed [START_REF] Hoàng | Some classes of perfectly orderable graphs[END_REF]; our contribution is that we restate the main condition on which their algorithm is based in terms of P 3 s participating in P 4 s of the input graph, and we show how to efficiently take advantage of it in order to achieve an O(nm)-time complexity. As described in the introduction, their algorithm works as follows: it initially sets H := V (G) and then it iteratively identifies a vertex x in H such that G does not contain a P 4 of the form abxc with b, c ∈ H, and removes it from H; the graph G is P 4 -simplicial iff the above process continues until H becomes the empty set. It is not difficult to see that the necessary property for a vertex x to be removed from H can be equivalently stated as follows: Property 4.1 Let H be the current set of vertices of a given graph G. Then, a vertex x can be removed from H if and only if there does not exist any P 3 bxc participating in a P 4 of G with b, c ∈ H.

In light of Property 4.1, we can obtain an algorithm for deciding whether a given graph G is P 4simplicial by keeping count, for each vertex v ∈ H, of the number of P 3 s bvc with b, c ∈ H which participate in P 4 s of G, and by removing a vertex x from H whenever the number of such P 3 s associated with x is 0. The proposed algorithm implements this idea; it takes advantage of the computation of the P 3 s in P 4 s of G in O(nm) time, and maintains an array N umP 3[ ] of size n, which stores for each vertex v in H the number of P 3 s bvc which participate in P 4 s of G and have b, c ∈ H. The input graph G is assumed to be given in adjacency list representation. In more detail, the algorithm works as follows. the beginning of the (i + 1)-st iteration. Let H i denote the current value of H at the beginning of the i-th iteration and let x be the vertex removed from L during the i-th iteration; then, H i+1 = H i -{x}. Clearly, the vertices v for which N umP 3[v] may be changed from the i-th to the (i + 1)-st iteration are those in H i+1 ∩ N (x); indeed, for any vertex w in H i+1 -N (x) = H i -N (x) -{x}, any P 3 awb with a, b ∈ H i will have a, b, w ∈ H i+1 , since a, b = x, and thus N umP 3[w] will remain unchanged. Now, let us consider a vertex v ∈ H i+1 ∩ N (x). At the beginning of the (i + 1)-st iteration, N umP 3[v] must be equal to the number of P 3 s avb participating in P 4 s of G with a, b ∈ H i+1 ; this is precisely the value of N umP 3[v] at the beginning of the i-th iteration minus the number of P 3 s xvz participating in P 4 s of G with z ∈ H i . Step 4b identifies these P 3 s and decrements N umP 3[v] by 1 for each one of them. Note that N umP 3[v] will be decremented exactly once for each P 3 avb: if we assume, without loss of generality, that a is removed from H before b, then N umP 3[v] will be decremented during the processing of a; when b is processed, the P 3 avb will not be taken into account, even if v still belongs to H, because a / ∈ H. ✷

Then, the correctness of the algorithm follows from the correctness of the algorithm of Hoàng and Reed, from Lemma 2.3, Property 4.1, and the fact that at any given time the list L contains precisely those vertices that can be removed from H (a vertex x is inserted in L if and only if N umP 3[x] = 0, i.e., there does not exist any P 3 bxc participating in a P 4 of G with b, c ∈ H).

Providing a Certificate

As in the case of the bipolarizable graph recognition algorithm, the above algorithm can be made to return a certificate whenever it decides that the input graph G is not P 4 -simplicial. In particular, it could return the value of the set H, which would indicate a subgraph of G none of whose vertices can be removed in the sense of Property 4.1. Clearly, this does not require any additional computation time and space. However, it would be more interesting if the algorithm located a minimal such subset H ′ of H, that is, a subset H ′ such that every vertex y of H ′ forms a P 3 xyz participating in a P 4 of the input graph with x, z ∈ H ′ . To see the benefits of this, consider for example that the input graph G contained two domino graphs sharing an edge. Since the domino graph is a forbidden subgraph for the class of P 4simplicial graphs, the algorithm would stop, would report that G is not P 4 -simplicial and would return a set H of vertices which would be a superset of the set of vertices of both domino graphs. If however a minimal such set of vertices were returned, then one would be very close to identifying a forbidden subgraph in G. This approach, although very interesting, is hindered in part by the fact that no complete characterization of the P 4 -simplicial graphs by forbidden subgraphs is currently available in the literature. As a first attempt towards obtaining such a characterization, we found in an exhaustive fashion that all the forbidden subgraphs for the class of P 4 -simplicial graphs on up to 7 vertices are those shown in Figure 6.

Class Inclusions and Recognition Time Complexities

Figure 7 shows a diagram of class inclusions for a number of perfectly orderable classes of graphs and the currently best time complexities to recognize members of these classes. For definitions of the classes shown, see [2; 8]; note that the P 4 -free and the chordal graphs are also known as co-graphs and triangulated graphs respectively. In the diagram, there exists an arc from a class A to a class B if and only if B is a proper subset of A. Hence, if two classes are not connected by an arc, then each of these classes contains graphs not belonging to the other class (there are such sample graphs for each pair of non-linked classes).

Most of these class inclusions can be found in [START_REF] Brandstädt | Graph classes: A survey[END_REF] where a similar diagram with many more graph classes appears; Figure 7 comes from a portion of the diagram in [START_REF] Brandstädt | Graph classes: A survey[END_REF] augmented with the introduction of the inclusion relations for the classes of P 4 -simplicial, bipolarizable, and P 4 -indifference graphs, as described in Lemmata 5.1-5.3. We will show next that the class of weak bipolarizable graphs [START_REF] Olariu | Weak bipolarizable graphs[END_REF] is a proper subset of the class of P 4 -simplicial graphs. In fact, we show a slightly stronger result as established in the following proposition. Proposition 5.1 Let G be a weak bipolarizable graph and let v be a vertex of G. Then, G admits a P 4 -simplicial order ≺ on its vertices such that v ≺ x for any vertex x of G other than v.

Proof: We apply induction on the size of the graph by taking advantage of Theorem 1 of [START_REF] Olariu | Weak bipolarizable graphs[END_REF] which states that a graph G is weak bipolarizable if and only if every induced subgraph of G is chordal or contains a homogeneous set. For the basis step, it is not difficult to verify that every weak bipolarizable graph on up to 3 vertices admits a P 4 -simplicial order as described, since G does not contain any P 4 s. Next, we assume that the proposition holds for all weak bipolarizable graphs on up to k ≥ 3 vertices; we will show that any weak bipolarizable graph on k + 1 vertices admits a P 4 -simplicial order as described. Let G be since O(n + m) time suffices to determine whether a graph is chordal and to compute a homogeneous set (by means of modular decomposition [21; 6]), if one exists, the stated time complexity can be seen to be O(nm).

Concluding Remarks

We have presented recognition algorithms for the classes of bipolarizable (also known as Raspail) and P 4 -simplicial graphs running in O(nm) time, where n and m are the number of vertices and of edges of the input graph. Our proposed algorithms are simple, use simple data structures and require O(n + m) space; the algorithms can also be augmented so that they return a certificate, whenever they decide that the input graph is not bipolarizable or P 4 -simplicial, in O(n + m) additional time and space. We have also presented results on class inclusions and recognition time complexities for a number of perfectly orderable classes of graphs.

We leave as an open problem the designing of o(nm)-time algorithms for recognizing bipolarizable and/or P 4 -simplicial graphs. In light of the linear-time recognition of P 4 -indifference graphs [10; 26], it would be worth investigating whether the recognition of P 4 -comparability, P 4 -simplicial, and bipolarizable graphs is inherently more difficult; it must be noted that the approach used in [10; 26] is different from those used for the recognition of the remaining classes as it reduces in part the problem to the recognition of interval graphs which can be carried out in linear time.

Finally, another interesting open problem is that of obtaining a characterization of the P 4 -simplicial graphs by forbidden subgraphs. We note that any forbidden subgraph for the class of P 4 -simplicial graphs other than a C k for k ≥ 5, an A, and a D 6 contains an induced house (see Figure 6): if it did not, then it would be weak bipolarizable [START_REF] Olariu | Weak bipolarizable graphs[END_REF], and hence a P 4 -simplicial graph due to Lemma 5.1.

  Fig. 1::

4

 4 abcd has either (a ≺ b, b ≺ c, c ≺ d) or (d ≺ c, c ≺ b, b ≺ a);

4

 4 abcd has either (a ≺ b, c ≺ b, c ≺ d) or (b ≺ a, b ≺ c, d ≺ c).

1 .

 1 The input graph G is assumed to be given in adjacency list representation. The algorithm uses two arrays, an array M [ ] and an array S[ ], of size 2m each. The array M [ ] has entries M [xy] and M [yx], for each edge xy of G; the entry M [xy] is equal to 1 if there exist P 3 s xyz participating in P 4 s of G, and is equal to 0 otherwise. As a result, for an edge xy, both M [xy] and M [yx] are equal to 1 iff there exist P 3 s xyz and txy participating in P 4 s of G. The array S[ ] too has entries S[xy] and S[yx], for each edge xy of G; the entry S[xy] is equal to the index number of the partition set of N (y) to which x belongs (see Lemma 2.3). As a result, a path xyz is a P 3 participating in P 4 s of G iff S[xy] = 0, S[zy] = 0, and S[xy] = S[zy]. In more detail, the algorithm works as follows.

1 .

 1 Initialize the entries of the arrays M [ ] and S[ ] to 0; for each vertex v, sort the records of the neighbors of v in v's adjacency list in increasing vertex index number; 2. Find all the P 3 s participating in P 4 s of G; for each such P 3 abc, set the entries M [ab] and M [cb] equal to 1, and appropriately update the entries S[ab] and S[cb]; 3. for each edge uv of G such that M [uv] = 1 and M [vu] = 1 do (a) traverse the adjacency lists of u and v in lockstep fashion and process the neighbors of v which are not neighbors of u, and the neighbors of u which are not neighbors of v as follows: (b) for each neighbor w of v in G which is not adjacent to u do if S[uv] = 0 and S[wv] = 0 and S[uv] = S[wv

Theorem 3 . 1

 31 Let G be an undirected graph on n vertices and m edges. Then, our algorithm determines whether G is a bipolarizable graph in O(nm) time and O(n + m) space.

  receive opposite orientations. Suppose now that an edge ab receives opposite orientations. Then, G contains P 4 s abcd and xyab; clearly y differs from c and d, x differ from both c and y. If d coincides with x, then the vertices a, b, c, d, y induce a C 5 or a house in G. If d differs from x, then if d, y or c, x are adjacent in G a C 5 or a house is induced, otherwise G contains an induced P 6 , A, C 6 , or D 6 .✷

4

 4 Fig. 2::

Lemma 3 . 4

 34 Let G be a graph which contains no C 5 , house, P 6 , A, C 6 , or D 6 . Then, if G contains a z-triomino then the directed graph -→ G exhibits a directed cycle on 4 vertices with a single undirected diagonal. Conversely, if -→ G exhibits a directed cycle bgf c (directed from b to g to f to c to b) with a single undirected diagonal bf , then for any P 4 s ahgf and bcde of G, the vertices a, b, c, d, e, f, g, h induce a z-triomino in G.

  (a) the edge bf participates in a P 4 xabf : Then, xc ∈ E(G), otherwise the path xabc would be a P 4 whose wing bc would be oriented towards b in -→ G . But then, f cxa would be a P 4 with both its wings oriented away from its endpoints; a contradiction. (b) the edge bf participates in a P 4 xhbf : Then, again xc ∈ E(G), otherwise the path xhbc would be a P 4 whose wing bc would be oriented towards b in -→ G . And again, f cxh would be a P 4 with both its wings oriented away from its endpoints; a contradiction. (c) the edge bf participates in a P 4 xybf : Then, at least one of xc and yc belongs to E(G), otherwise the path xybc would be a P 4 whose wing bc would be oriented towards b. In fact, yc ∈ E(G), for otherwise the existence of xc would imply that the vertices x, y, b, c, f induce a house graph in G.

  Fig. 4::

A

  . a conflict of orientation is found on an edge vw (Steps 3.2, 3.3): A.1 locate P 4 s abvw and vwxy of G; A.2 if a = y then return as forbidden subgraph the subgraph G[{a, b, v, w, x}]; else return as forbidden subgraph the subgraph G[{a, b, v, w, x, y}]; B. a directed cycle is detected in the directed graph -→ G (Step 4): B.1 locate a directed cycle with no directed chords; B.2 if this is a directed cycle bgf c with a single undirected diagonal bf then locate P 4 s ahgf and bcde of G; return as forbidden subgraph the subgraph G[{a, b, c, d, e, f, g, h}; else {the vertices of the cycle induce a complete subgraph of G} return the k-wheel built around the directed cycle, where k is the length of the cycle;

4 Theorem 3 . 2

 432 Fig. 5::

  Time and Space Complexity. The set H can be implemented by means of an array M [ ] of size n, where M [v] = 1 if v ∈ H and 0 otherwise; in this way, insertion, deletion, and membership queries for any vertex of G can be answered in constant time, while the emptiness of H can be checked in O(n) time. Then, Step 1 takes O(n + m) time, Step 4c takes O(1) time per vertex removed, and Step 5 O(n) time. Step 2 takes O(nm) time [23], while Step 3 takes O(n) time. As a vertex is inserted at most once in the list L, the time complexity of Step 4 is O x 1 + u∈N (x) deg(u) , where deg(u) denotes the degree of u in G. Since u∈N (x) deg(u) = O(m), the time complexity of Step 4 is O(nm). The computation of the P 3 s participating in P 4 s takes linear space, and thus the total space needed by the recognition algorithm is clearly linear in the size of the input graph G.Summarizing, we obtain the following theorem. Theorem 4.1 Let G be an undirected graph on n vertices and m edges. Then, our algorithm determines whether G is a P 4 -simplicial graph in O(nm) time and O(n + m) space.

Fig. 6 :

 6 Fig.6: Some forbidden subgraphs for the class of P4-simplicial graphs.

  ] then {uvw is a P 3 in a P 4 of G} if the edge vw has not yet received an orientation then orient it towards w; else if it is oriented towards v then print that G is not a bipolarizable graph; exit; (c) for each neighbor w of u in G which is not adjacent to v do if S[vu] = 0 and S[wu] = 0 and S[vu] = S[wu] then {vuw is a P 3 in a P 4 of G} if the edge uw has not yet received an orientation then orient it towards w; else if it is oriented towards u then print that G is not a bipolarizable graph; exit; 4. Check if the directed subgraph -→ G spanned by the oriented edges contains a directed cycle; if it does not, print that G is a bipolarizable graph; otherwise, print that it is not.

1365-8050 c 2005 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

The vertices that remain in the list L after the procedure get c-d-cycle(L) has completed induce a directed cycle without directed chords in the directed subgraph -→ G . The correctness of the computation follows easily: the three cases of clipping are illustrated in Figure 5, where the dashed edge at the top indicates the edge directed from the last vertex of the list L to its first vertex and the shaded regions are the portions of the list L that are removed during the processing of vertex x in each case. It is important to observe that the clipping indeed maintains the ordering of the "ranks" of the vertices along the list L, and that after a vertex x has been processed the resulting list L induces a directed cycle without directed chords incident on x.

Locating a k-wheel.

If the directed cycle in the list L that the procedure get c-d-cycle( ) has located is not a cycle on 4 vertices with a single diagonal but instead is a C k (k ≥ 3) induced by the vertex set P = {v 0 , v 1 , . . . , v k-1 } in order along the C k , we can obtain the complete k-wheel built around the C k . If we try to find a P 4 s i r i v i v i-1 for each pair v i , v i-1 , this might require Ω(k(n + m)) time, which may be superlinear in max{n, m}. Instead, we can obtain a linear time complexity by using an array A[ ] of size n and by working as follows:

1. mark the entries of A[ ] corresponding to the vertices v 0 , v 1 , . . . , v k-1 of the set P ; form empty sets R 0 , R 1 , . . . , R k-1 and S 0 , S 1 , . . . , S k-1 ;

2. for each vertex x / ∈ P do p x ← number of vertices in P which are neighbors of x in G;

then if the only vertices in P which are not neighbors of x in G are v i , v i-1 mod k then insert x in the set S i ;

3. let B[ ] be an empty array of size n; for i = 0, 1, . . . , k -1 do mark the entries of B[ ] corresponding to the vertices in the set S i ;

unmark the entries of B[ ] corresponding to the vertices in S i ; proceed with next value of i;

4. the vertices in P and the collected vertices r i and s i induce a k-wheel in G.

It is important to observe that the vertex sets R 0 , R 1 , . . . , R k-1 and S 0 , S 1 , . . . , S k-1 are distinct from one another and from P due to their adjacencies to the vertices in P ; thus, storing all these sets in linked lists takes O(n) space. Moreover, for each i, the vertices v i , v i-1 , r i , s i induce a P 4 s i r i v i v i-1 in G; thus, by Lemma 3.6, the process indeed finds a wheel.

P 4 -simplicial Graph Recognition Algorithm

Input: an undirected graph G on n vertices and m edges. Output: a message as to whether G is a P 4 -simplicial graph or not.

if the set H is empty

then print that G is a P 4 -simplicial graph; else print that G is not a P 4 -simplicial graph;

To ensure correct execution, the algorithm maintains the following invariant throughout the execution of Step 4. Proof: The proof proceeds inductively in the number of iterations of the while loop.

Step 2 clearly implies that the invariant holds at the begin of the first iteration of the loop, since H = V (G). Suppose now that the invariant holds at the beginning of the i-th iteration, where i ≥ 1; we will show that it also holds at If G is not chordal, then from [START_REF] Olariu | Weak bipolarizable graphs[END_REF] we have that G contains a homogeneous set. Let S be a minimal such homogeneous set and let u be a vertex in S; if v ∈ S, we choose u to be v. Then, the subgraph G u of G induced by the vertices in V (G) -V (S) ∪ {u} is also a weak bipolarizable graph which contains v and has at most k vertices, since |V (S)| ≥ 2. By our inductive hypothesis, G u admits a P 4 -simplicial order ≺ such that v ≺ x for all vertices x ∈ V (G u ) -{v}. On the other hand, the subgraph G[S] is chordal, because it is a subgraph of a weak bipolarizable graph and S was chosen to be minimal [START_REF] Olariu | Weak bipolarizable graphs[END_REF]. If we replace u in the P 4 -simplicial order ≺ of the subgraph G u by the reverse of the ordering of the vertices of S which implements a perfect elimination scheme on S produced by the LexBFS algorithm starting at u, we are guaranteed to obtain a P 4 -simplicial ordering of the vertices of G as desired. The inductive proof is complete, and thus every weak bipolarizable graph admits a P 4 -simplicial order meeting the conditions of the statement of the proposition. ✷

We are now ready to prove the inclusion relations of the class of P 4 -simplicial graphs.

Lemma 5.1 The class of P 4 -simplicial graphs is a proper subset of the class of brittle graphs and a proper superset of the class of weak bipolarizable graphs.

Proof: The fact that P 4 -simplicial ⊆ Brittle has been shown in [START_REF] Hoàng | Some classes of perfectly orderable graphs[END_REF]; to see that the subset relation is proper, simply consider the graph D 6 of Figure 1 which is brittle but not P 4 -simplicial. On the other hand, Proposition 5.1 establishes that Weak Bipolarizable ⊆ P 4 -simplicial. The proper inclusion follows from the fact that the house graph is P 4 -simplicial but not weak bipolarizable. ✷

Regarding the relation of P 4 -simplicial and the HHD-free and co-chordal graphs, note that the graph D 6 of Figure 1 is both HHD-free and co-chordal but is not P 4 -simplicial whereas the house graph and P 5 are P 4 -simplicial but not HHD-free and not co-chordal respectively.

Lemma 5.2 The class of bipolarizable graphs is a proper subset of the class of weak bipolarizable graphs and a proper superset of the classes of P 4 -sparse and split graphs.

Proof: The fact that Bipolarizable ⊂ Weak Bipolarizable has been established in [START_REF] Olariu | Weak bipolarizable graphs[END_REF]. To establish the relationship of P 4 -sparse and bipolarizable graphs, we note that none of the forbidden subgraphs for the class of bipolarizable graphs is P 4 -sparse; see Figure 1 and note that a k-wheel of order k ≥ 2 contains the P 5 s 0 r 0 v 0 v k-1 r 1 . This implies that any graph which is not bipolarizable cannot be P 4sparse, or conversely that P 4 -sparse ⊆ Bipolarizable. The proper inclusion follows from the fact that a P 5 is bipolarizable but not P 4 -sparse.

It is not difficult to see that Split ⊆ Bipolarizable; the vertex set of a split graph can be partitioned into an independent set and a clique, which implies that any P 4 of a split graph has its midpoints in the clique and its endpoints in the independent set. Thus any ordering of the vertices of a split graph where all the vertices of the clique precede all the vertices of the independent set gives a bipolarizable ordering of the graph. The proper inclusion follows from the fact that C 4 is bipolarizable but not split. ✷ Lemma 5.3 The class of P 4 -indifference graphs is a proper subset of the class of weak bipolarizable graphs and a proper superset of the class of P 4 -reducible graphs.

Proof: The fact that P 4 -indifference ⊂ Weak Bipolarizable follows from the fact that the set of forbidden subgraphs for the class of weak bipolarizable graphs is a proper subset of the set of forbidden subgraphs for the class of P 4 -indifference graphs (compare [START_REF] Olariu | Weak bipolarizable graphs[END_REF] and [START_REF] Hoàng | A characterization of P 4 -indifference graphs[END_REF]).

To see that P 4 -reducible ⊆ P 4 -indifference, we recall that every vertex of a P 4 -reducible belongs to at most one P 4 , which implies that the P 4 s of a P 4 -reducible graph are vertex-disjoint. Thus, we can create a linear order of the vertices of such a graph by concatenating the vertices of each P 4 at a time, in the order they appear along the P 4 , and by appending any remaining vertices; then, the resulting ordering is a P 4 -indifference ordering of the vertices of the graph. The proper inclusion follows from the fact that the P 5 is a P 4 -indifference graph but not P 4 -reducible. ✷

The non-inclusion relation between bipolarizable and co-chordal graphs follows from the counterexamples for the non-inclusion relation of the P 4 -simplicial and co-chordal graphs. A non-inclusion relation also holds for the bipolarizable and the chordal graphs (consider a C 4 and the z-triomino) and for the bipolarizable and the P 4 -indifference graphs (consider the forbidden subgraphs F 5 of [START_REF] Hoàng | A characterization of P 4 -indifference graphs[END_REF] and the z-triomino).

In Figure 7, we have also partitioned the depicted classes of graphs based on the time complexities of the currently best recognition algorithms: see [7; 28] for the O(min{m 2 , n 3 log 2 n})-time complexity range, [START_REF] Nikolopoulos | Recognizing HHD-free and Welsh-Powell opposition graphs[END_REF] for the O(min{nmα(n), nm + n 2 log n})-time complexity range, [23; 25] for the O(nm)time complexity range, and [10; 26; 19; 20; 5; 27; 9; 11] for the O(n + m)-time range. We note that the algorithm of [START_REF] Olariu | Weak bipolarizable graphs[END_REF] for the recognition of weak bipolarizable graphs has a stated time complexity of O(n 3 );


David R Wood
email: david.wood@upc.edu

Queue Layouts of Graph Products and Powers †

Keywords: graph, queue layout, cartesian product, d-dimensional grid graph, d-dimensional toroidal grid graph, Hamming graph. 2000 MSC classification: 05C62 (graph representations)

A k-queue layout of a graph G consists of a linear order σ of V (G), and a partition of E(G) into k sets, each of which contains no two edges that are nested in σ. This paper studies queue layouts of graph products and powers.

Introduction

Let G be a graph. (All graphs considered are finite, simple and undirected.) The vertex and edge sets of G are denoted by V (G) and E(G), respectively. The minimum and maximum degree of G are denoted by δ(G) and ∆(G), respectively. The density of G is η(G) := |E(G)|/|V (G)|.

A vertex ordering of G is a bijection σ : V (G) → {1, 2, . . . , |V (G)|}. In a vertex ordering σ of G, let L σ (e) and R σ (e) denote the endpoints of each edge e ∈ E(G) such that σ(L σ (e)) < σ(R σ (e)).

Where the vertex ordering σ is clear from the context, we will abbreviate L σ (e) and R σ (e) by L e and R e , respectively. For edges e and f of G with no endpoint in common, there are the following three possible relations with respect to σ, as illustrated in Figure 1: (a) e and f nest if σ(L e ) < σ(L f ) < σ(R f ) < σ(R e ), (b) e and f cross if σ(L e ) < σ(L f ) < σ(R e ) < σ(R f ), (c) e and f are disjoint if σ(L e ) < σ(R e ) < σ(L f ) < σ(R f ). A queue in σ is a set of edges Q ⊆ E(G) such that no two edges in Q are nested. Observe that when traversing σ from left to right, the left and right endpoints of the edges in a queue are reached in first-infirst-out order-hence the name 'queue'. Observe that Q ⊆ E(G) is a queue if and only if for all edges e, f ∈ Q, σ(L e ) ≤ σ(L f ) and σ(R e ) ≤ σ(R f ) ,

(1) or σ(L f ) ≤ σ(L e ) and σ(R f ) ≤ σ(R e ) .

A k-queue layout of G is a pair

(σ, {Q 1 , Q 2 , . . . , Q k })
where σ is a vertex ordering of G, and {Q 1 , Q 2 , . . . , Q k } is a partition of E(G), such that each Q i is a queue in σ. The queue-number of a graph G, denoted by qn(G), is the minimum k such that there is a k-queue layout of G.

Queue layouts were introduced by Heath et al. [START_REF] Heath | Comparing queues and stacks as mechanisms for laying out graphs[END_REF][START_REF] Heath | Laying out graphs using queues[END_REF]. Applications of queue layouts include sorting permutations [START_REF] Even | Queues, stacks, and graphs[END_REF][START_REF] Nozaki | Generating and sorting permutations using restricteddeques[END_REF][START_REF] Ordman | Permutations using stacks and queues[END_REF][START_REF] Vaughan | Computing permutations with double-ended queues. Parallel stacks and parallel queues[END_REF][START_REF] Tarjan | Sorting using networks of queues and stacks[END_REF], parallel process scheduling [START_REF] Sandeep | Scheduling tree-dags using FIFO queues: A control-memory trade-off[END_REF], matrix computations [START_REF] Pemmaraju | Exploring the Powers of Stacks and Queues via Graph Layouts[END_REF], and graph drawing [START_REF] Di | Computing straight-line 3D grid drawings of graphs in linear volume[END_REF][START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF]. Other aspects of queue layouts have been studied in the literature [START_REF] Vida Dujmovi | Track layouts of graphs[END_REF][START_REF] Vida | On linear layouts of graphs[END_REF][START_REF] Vida | Stacks, queues and tracks: Layouts of graph subdivisions[END_REF][START_REF] Ganley | Stack and queue layouts of Halin graphs[END_REF][START_REF] Madhavan | Stack and queue number of 2-trees[END_REF][START_REF] Shi | On crossing sets, disjoint sets, and pagenumber[END_REF]. Queue layouts of directed graphs [START_REF] Di | Volume requirements of 3D upward drawings[END_REF][START_REF] Vida | Three-dimensional upward grid drawings of graphs[END_REF][START_REF] Heath | Stack and queue layouts of directed acyclic graphs. part II[END_REF][START_REF] Heath | Stack and queue layouts of directed acyclic graphs. part I[END_REF] and posets [START_REF] Heath | Stack and queue layouts of posets[END_REF] have also been investigated.

Table 1 describes the best known upper bounds on the queue-number of various classes of graphs. Planar graphs are an interesting class of graphs for which it is not known whether the queue-number is bounded (see [START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF][START_REF] Pemmaraju | Exploring the Powers of Stacks and Queues via Graph Layouts[END_REF]).

This paper studies queue layouts of graph products and graph powers. To prove optimality we use the following lower bound by Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF]. See Pemmaraju [START_REF] Pemmaraju | Exploring the Powers of Stacks and Queues via Graph Layouts[END_REF] and Dujmović and Wood [START_REF] Vida | On linear layouts of graphs[END_REF] for slightly more exact lower bounds.

Lemma 1 ([19]) Every graph G has queue-number qn(G) > η(G)/2.
This paper is organised as follows. In Section 2 we introduce the concepts of strict queue layout and strict queue-number. Many of the upper bounds on the queue-number that are presented in later sections will be expressed as functions of the strict queue-number. In Section 3 we prove bounds on the queuenumber of the power of a graph in terms of the queue-number of the underlying graph. In Section 4 we define the graph products that will be studied in later sections. In Section 5 we study the queue-number of the cartesian product of graphs. Finally in Section 6 we study the queue-number of the direct and strong products of graphs. ‡ Dujmović and Wood [START_REF] Vida | Tree-partitions of k-trees with applications in graph layout[END_REF] gave a simple proof of this result. 2 Strict Queue Layouts

Let σ be a vertex ordering of a graph G. We say an edge e is inside a distinct edge f , and e and f overlap,

if σ(L f ) ≤ σ(L e ) < σ(R e ) ≤ σ(R f ) . A set of edges Q ⊆ E(G) is a strict queue in σ if no edge in Q is inside another edge in Q. Alternatively, Q is a strict queue in σ if σ(L e ) < σ(L f ) and σ(R e ) < σ(R f ) , (2) or σ(L f ) < σ(L e ) and σ(R f ) < σ(R e ) .
Note that Equation (2) is obtained from Equation (1) by replacing "≤" by "<".

Hence a strict queue is a set of edges, no two of which are nested or overlapping, as illustrated in Figure 2. Note that edges forming a 'butterfly' can be in a single strict queue. A strict k-queue layout of G is a pair (σ, {Q 1 , Q 2 , . . . , Q k }) where σ is a vertex ordering of G, and {Q 1 , Q 2 , . . . , Q k } is a partition of E(G), such that each Q i is a strict queue in σ. We sometimes write queue(e) = i for each edge e ∈ Q i . The strict-queue-number of a graph G, denoted by sqn(G), is the minimum k such that there is a strict k-queue layout of G.

Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF] proved that a fixed vertex ordering of a graph G admits a k-queue layout of G if and only if it has no (k + 1)-edge rainbow, where a rainbow is a set of pairwise nested edges, as illustrated in Figure 3(a). Consider the analogous problem for strict queues: assign the edges of a graph G to the minimum number of strict queues given a fixed vertex ordering σ of G. As illustrated in Figure 3(b), a weak rainbow in σ is a set of edges R such that for every pair of edges e, f ∈ R, e is inside f or f is inside e. Proof: A strict k-queue layout has no (k + 1)-edge weak rainbow since each edge of a weak rainbow must be in a distinct strict queue. Conversely, suppose we have a vertex ordering with no (k + 1)-edge weak rainbow. For every edge e ∈ E(G), let queue(e) be one plus the maximum number of edges in a weak rainbow consisting of edges that are inside e. If e is inside f then queue(e) < queue(f ). Hence we have a valid strict queue assignment. The number of strict queues is at most k. ✷

A linear forest is a graph in which every component is a path. The linear arboricity of a graph G, denoted by la(G), is the minimum integer k such that E(G) can be partitioned in k linear forests; see [START_REF] Alon | The linear arboricity of graphs[END_REF][START_REF] Noga Alon | Linear arboricity and linear k-arboricity of regular graphs[END_REF][START_REF] Wu | On the linear arboricity of planar graphs[END_REF][START_REF] Wu | The linear arboricity of series-parallel graphs[END_REF]. We have the following lower bounds on sqn(G).

Lemma 3

The strict queue-number of every graph G satisfies:

(a) sqn(G) ≥ la(G) > η(G), (b) sqn(G) ≥ la(G) ≥ ∆(G)/2, and (c) sqn(G) ≥ δ(G). Proof: Say Q is a strict queue in a vertex ordering σ of G. Every 2-edge path (u, v, w) in Q has σ(u) < σ(v) < σ(w) (or σ(w) < σ(v) < σ(u)).
Thus no vertex is incident to three edges in Q, and Q induces a linear forest. Hence la(G) ≤ sqn(G).

Since a linear forest in G has at most

|V (G)| -1 edges, la(G) ≥ |E(G)|/(|V (G)| -1) > η(G)
. This proves (a). At most two edges incident to each vertex are a linear forest. Thus la(G) ≥ ∆(G)/2. This proves (b).

In every vertex ordering of G, every edge incident to the first vertex is in a distinct strict queue. Hence sqn(G) ≥ δ(G). This proves (c). ✷

Obviously a proper edge (∆(G) + 1)-colouring [START_REF] Vadim | On an estimate of the chromatic class of a p-graph[END_REF] can be combined with a qn(G)-queue layout to obtain a strict queue layout.

Lemma 4 Every graph G has strict queue-number sqn(G) ≤ (∆(G) + 1) • qn(G). ✷

Graph Powers

Let G be a graph, and let d ∈ Z + . The d-th power of G, denoted by G d , is the graph with vertex set

V (G d ) = V (G)
, where vw ∈ E(G d ) if and only if the distance between v and w in G is at most d. The following general result is similar to a theorem of Dujmović and Wood [START_REF] Vida | Stacks, queues and tracks: Layouts of graph subdivisions[END_REF].

Theorem 1 For every graph G and

d ∈ Z + , qn(G d ) ≤ (2 sqn(G)) d+1 -1 2 sqn(G) -1 -sqn(G) -1 .
Proof: Let σ be the vertex ordering in a strict sqn(G)-queue layout of G. Consider σ to be a vertex ordering of G d . For every pair of vertices v, w ∈ V (G) with σ(v) < σ(w) and at distance ℓ ≤ d, fix a path P (vw) from v to w in G with exactly ℓ edges. Suppose P (vw) = (x 0 , x 1 , . . . , x ℓ ), where v = x 0 and w = x ℓ . For each

1 ≤ i ≤ ℓ, let dir(x i-1 x i ) be '+' if σ(x i-1 ) < σ(x i )
, and '-' otherwise. Let f (vw) be the vector

f (vw) = queue(x i-1 x i ), dir(x i-1 x i ) : 1 ≤ i ≤ ℓ .
Consider two edges vw, pq ∈ E(G d ) with f (vw) = f (pq). Then |P (vw)| = |P (pq)|. Let P (vw) = (x 0 , x 1 , . . . , x ℓ ) and P (pq) = (y 0 , y 1 , . . . , y ℓ ). We have dir(x 0 x 1 ) = dir(y 0 y 1 ) and queue(x 0 x 1 ) = queue(y 0 y 1 ). Thus x 0 = y 0 . Without loss of generality σ(x 0 ) < σ(y 0 ). By Equation (2), σ(x 1 ) < σ(y 1 ). In general, σ(x i-1 ) < σ(y i-1 ) implies σ(x i ) < σ(y i ), since queue(x i-1 x i ) = queue(y i-1 y i ) and dir(x i-1 x i ) = dir(y i-1 y i ). By induction, σ(x i ) < σ(y i ) for all 0 ≤ i ≤ ℓ. In particular, σ(w) < σ(q). Thus vw and pq can be in the same strict queue. If we partition the edges of G d by the value of f we obtain a strict queue layout of G d . The number of queues is

d ℓ=1 (2 sqn(G)) ℓ = (2 sqn(G)) d+1 -1 2 sqn(G) -1 -1 .
Observe that for the edges of G we have counted 2 sqn(G) queues. Of course we need only sqn(G) queues. Thus the total number of queues is as claimed. ✷

Powers of Paths and Cycles

In a vertex ordering σ of a graph G, the width of an edge e is σ(R e ) -σ(L e ). The bandwidth of σ is the maximum width of an edge of G. The bandwidth of G, denoted by bw(G), is the minimum bandwidth of a vertex ordering of G. Alternatively, bw(G) = min{k : G ⊆ P k n } for every n-vertex graph G.

Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF] observed that edges whose widths differ by at most one are not nested. Thus qn(G) ≤ ⌈bw(G)/2⌉, as mentioned in Table 1. In a vertex ordering, edges with the same width are not nested or overlapping, and thus form a strict queue. The next lemma follows.

Lemma 5 Every graph G has strict queue-number sqn(G) ≤ bw(G). ✷

We have the following results that give more precise bounds on the queue-number and strict-queuenumber of powers of paths and cycles than Theorem 1.

Lemma 6

The k-th power of a path P n (n ≥ k + 1) has queue-number qn(P k n ) = ⌈k/2⌉ and strict queue-number sqn(P k n ) = k

Proof: The bandwidth of a graph G can be thought of as the minimum integer k such that G ⊆ P k n . Thus the upper bound is nothing more than the result qn(G) ≤ ⌈bw(G)/2⌉ of Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF]. The lower bound follows since P k n contains a (k + 1)-clique, which contains ⌈k/2⌉ pairwise nested edges in any vertex ordering, all of which must be assigned to distinct queues.

The natural vertex-ordering of P k n has no (k +1)-edge weak rainbow. Thus sqn(P k n ) ≤ k by Lemma 2. The lower bound follows since P k n contains a (k + 1)-clique, which contains a k-edge weak rainbow in any vertex ordering. ✷

A graph is unicyclic if every connected component has at most one cycle. Heath and Rosenberg [START_REF] Heath | Laying out graphs using queues[END_REF] proved that any unicyclic graph has a 1-queue layout. In particular, every cycle has a 1-queue layout. More generally,

Lemma 7 The k-th power of a cycle C n (n ≥ 2k) has queue-number k 2 < qn(C k n ) ≤ k, and strict queue-number sqn(C k n ) = 2k. Proof: Observe that δ(C k n ) = ∆(C k n ) = 2k and η(C k n ) = k.
Thus the claimed lower bounds follow from Lemmata 1 and 3. For the upper bounds, say C n = (v 1 , v 2 , . . . , v n ). By considering the vertex ordering

(v 1 , v n ; v 2 , v n-1 ; . . . ; v i , v n-i+1 ; . . . ; v ⌊n/2⌋ , v ⌈n/2⌉ ) , (3)
we see that C k n ⊂ P 2k n . The result follows from Lemma 6. ✷

Graph Products

Let G 1 and G 2 be graphs. Below we define a number of graph products whose vertex set is

V (G 1 ) × V (G 2 ) = {(a, v) : a ∈ V (G 1 ), v ∈ V (G 2 )}) .
We classify a potential edge (a, v)(b, w) as follows:

• G 1 -edge: ab ∈ E(G 1 ) and v = w.
• G 2 -edge: a = b and vw ∈ E(G 2 ).

• direct edge: ab ∈ E(G 1 ) and vw ∈ E(G 2 ).

The cartesian product G 1 G 2 consists of the G 1 -edges and the G 2 -edges. The direct product G 1 ×G 2 consists of the direct edges. The strong product G 1 ⊠ G 2 consists of the G 1 -edges, the G 2 -edges, and the direct edges. That is,

G 1 ⊠ G 2 = (G 1 G 2 ) ∪ (G 1 × G 2 )
. Note that other names abound for these graph products. Our notation is taken from the survey by Klavžar [START_REF] Klav Žar | Coloring graph products-a survey[END_REF]. Assuming isomorphic graphs are equal, each of the above three products are associative, and for instance, The following lemma is well-known and easily proved.

G 1 G 2 • • • G d is well-defined.
Lemma 8 For all graphs G 1 and G 2 , the density satisfies

(a) η(G 1 G 2 ) = η(G 1 ) + η(G 2 ), (b) η(G 1 × G 2 ) = 2η(G 1 ) • η(G 2 ), (c) η(G 1 ⊠ G 2 ) = 2η(G 1 ) • η(G 2 ) + η(G 1 ) + η(G 2 ).

The Cartesian Product

We have the following bounds on the queue-number of a cartesian product. In a vertex ordering σ of a graph product, we abbreviate σ((v, a)) by σ(v, a).

Theorem 2 For all graphs G and H, qn(G H) ≤ sqn(G) + qn(H) .

Theorem 3 For all d ≥ 2, the queue-number of a d-dimensional grid

G = P n1 P n2 • • • P n d satisfies: d 4 ≤ 1 2 d - d i=1 1 n i < qn(G) ≤ d -1 .
Proof: The lower bound follows from Lemma 1 and Equation ( 4) with k = 1.

For the upper bound, we have qn(P n1 P n2 ) = 1 by Lemma 9. Obviously sqn(P ni ) = 1 for all i ≥ 3. Thus qn(G) ≤ d -1 by Corollary 1.

We now give an alternative proof of the upper bound using a different construction. The graph G can be thought of as having vertex set {((x 1 , x 2 , . . . , x d ) : 1 ≤ x i ≤ n i , 1 ≤ i ≤ d}, where two vertices (x 1 , x 2 , . . . , x d ) and (y 1 , y 2 , . . . , y d ) are adjacent if and only if |x i -y i | = 1 for some i, and x j = y j for all j = i. We say this edge is in the i-th dimension. For all s ≥ 0, let V s be the set of vertices

V s = {(x 1 , x 2 , . . . , x d ) : d i=1 x i = s} .
Order the vertices (V 0 , V 1 , . . . ), where each V s is ordered lexicographically. If vw is an edge then v and w differ in exactly one coordinate, and v ∈ V s and w ∈ V s+1 for some s. Thus if two edges vw and pq are nested then v, p ∈ V s and w, q ∈ V s+1 for some s. Let Q i be the set of edges in the i-th dimension. Consider two edges e and f in Q i . Say

e = (x 1 , x 2 , . . . , x d )(x 1 , . . . , x i-1 , x i + 1, x i+1 , . . . , x d ) ,
and f = (y 1 , y 2 , . . . , y d )(y 1 , . . . , y i-1 , y i + 1, y i+1 , . . . , y d ) .

Without loss of generality (x 1 , x 2 , . . . , x d ) ≺ (y 1 , y 2 , . . . , y d ), which implies that (x 1 , . . . , x i-1 , x i + j, x i+1 , . . . , x d ) ≺ (y 1 , . . . , y i-1 , y i + j, y i+1 , . . . , y d ) .

Thus e and f are not nested, and Q i is a queue. Hence we have a d-queue layout. (At this point we have in fact proved that the lexicographical order admits a d-queue layout.) We now prove that Q d-1 ∪Q d is a queue, and thus we obtain the claimed (d-1)-queue layout. Suppose two edges e ∈ Q d-1 and f ∈ Q d are nested. Say Then for some s, both (x

e = (x 1 , x 2 , . . . , x d )(x 1 , x 2 , . . . , x d-1 + 1, x d ) ,
x i = i y i . Thus j = d -1. That is, x d-1 ≤ y d-1 -1 . (5)
Since e and f are nested, we have (y

dk 4 ≤ dk 2 - k(k + 1) 4 d i=1 1 n i < qn(G) ≤ (d - 1
2 )k .

Proof: By Lemma 6, qn(P k n ) = ⌈ k 2 ⌉ and sqn(P k n ) ≤ k. Thus, the upper bound follows from Corollary 1. Thus the lower bound follows from Lemma 1 and Equation [START_REF] Di | Computing straight-line 3D grid drawings of graphs in linear volume[END_REF]. ✷

By Theorem 4 with k = n -1 we have the following. We have the following bounds on the queue-number of direct and strong products.

Corollary 2 The queue-number of the d-dimensional Hamming graph

G = K n K n • • • K n satisfies: d(n -1) 4 < qn(G) ≤ (d -1 2 )(n -1) . A generalised d-dimensional toroidal grid is a graph C k n1 C k n2 • • • C k n d for all k ≥ 1 and n i ≥ 2k + 1.

Theorem 5 The queue-number of a generalised toroidal grid

G = C k n1 C k n2 • • • C k n d (where n i ≥ 2k + 1) satisfies: kd 2 < qn(G) ≤ (2d -
Theorem 6 For all graphs G and H,

qn(G × H) ≤ 2 sqn(G) • qn(H) . Furthermore, if sqn(G) ≤ c • η(G) and qn(H) ≤ c • η(H), then qn(G × H) > 1 c 2 sqn(G) • qn(H) .
Proof: First we prove the upper bound. Let k := sqn(G), and let (σ, {Q 1 , Q 2 , . . . , Q k }) be a strict k-queue layout of G. Let ℓ := qn(H), and let (π, {P 1 , P 2 , . . . , P ℓ }) be an ℓ-queue layout of H. For ✷

1 ≤ i ≤ k and 1 ≤ j ≤ ℓ, let E ′ i,j := {(v, a)(w, b) ∈ E(G × H) : vw ∈ Q i , ab ∈ P j , σ(v) < σ(w), π(a) < π(b)} E ′′ i,j := {(v, a)(w, b) ∈ E(G × H) : vw ∈ Q i , ab ∈ P j , σ(v) < σ(w), π(b) < π(a)} Then {E ′ i,j , E ′′ i,j : 1 ≤ i ≤ k, 1 ≤ j ≤ ℓ} is a partition of E(G ×

Fig. 1 :

 1 Fig.1: Relationships between pairs of edges with no common endpoint in a vertex ordering.

Fig. 2 :

 2 Fig.2: Relationships between pairs of edges with a common endpoint in a vertex ordering.

Fig. 3 :

 3 Fig. 3: (a) rainbow, (b) weak rainbow

Figure 4 4 Fig. 4 :

 444 Fig. 4: Examples of graph products: (a) cartesian, (b) direct, (c) strong.

and f = (y 1

 1 , y 2 , . . . , y d )(y 1 , y 2 , . . . , y d-1 , y d + 1) .

2 ⌋ + 1 .

 21 1)k . Proof: Since η(G) = kd, we have that qn(G) > kd 2 by Lemma 1. Thus qn(G) ≥ ⌊ d By Lemma 7, qn(C k n1 ) ≤ k and sqn(C k n1 ) ≤ 2k. By Corollary 1, qn(G) ≤ 2k(d -1) + k = (2d -1)k ✷ 6 Direct and Strong Products

Theorem 7

 7 H) into 2kℓ sets. Let φ be the vertex ordering of G × H in which φ(v, a) < φ(w, b) if and only if σ(v) < σ(w), or v = w and π(a) < π(b).We claim that each set E ′ i,j andE ′′ i,j is a queue in φ. Suppose that two edges (v, a)(w, b), (x, c)(y, d) ∈ E ′ i,j are nested. Without loss of generality, φ(v, a) < φ(x, c) < φ(y, d) < φ(w, b). If v = x and y = w, then σ(v) < σ(x) < σ(y) < σ(w), and the edges vw, xy ∈ Q i are nested in σ. If v = x and y = w, then σ(v) < σ(x) < σ(y) = σ(w), and the edges vw, xy ∈ Q i overlap in σ. If v = x and y = w, then σ(v) = σ(x) < σ(y) < σ(w), and the edges vw, xy ∈ Q i overlap in σ. Each of these outcomes contradict the assumption that Q i is a strict queue in σ. Otherwise v = x and y = w, in which case π(a) < π(c) < π(d) < π(b), and ab and cd are nested in π. This contradicts the assumption that P j is a queue in π. Thus each E ′ i,j is queue in φ. By symmetry, each E ′′ i,j is also a queue in φ. Now we prove the lower bound. Lemmata 1 and 8(b) imply thatqn(G × H) > η(G × H)/2 = η(G) • η(H) ≥ 1 c sqn(G) • 1 c qn(H) .✷ For all graphs G and H, qn(G ⊠ H) ≤ 2 sqn(G) • qn(H) + sqn(G) + qn(H) .

Furthermore, if

  sqn(G) ≤ c • η(G) and qn(H) ≤ c • η(H), then qn(G ⊠ H) > 1 c 2 sqn(G) • qn(H) + 1 2c sqn(G) + qn(H) .Proof: To prove the upper bound, observe that the vertex ordering φ defined in Theorems 2 and 6 is the same. By Theorem 2, φ admits a sqn(G) + qn(H)-queue layout of G H. By Theorem 6, φ admits a2 sqn(G) • qn(H)-queue layout of G × H. Since G ⊠ H = (G H) ∪ (G × H),φ admits the claimed queue layout of G ⊠ H. For the lower bound, Lemmata 1 and 8(c) imply that qn(G ⊠ H) > 1 2 η(G ⊠ H) = η(G) • η(H) + 1 2 (η(G) + η(H))

  Tab. 1: Upper bounds on the queue-number.

	graph family	queue-number	reference
	n vertices m edges tree-width w tree-width w, max. degree ∆	⌊ n 2 ⌋ e √ m 3 w • 6 (4 w -3w-1)/9 -1 Dujmović et al. [6] Heath and Rosenberg [19] Dujmović and Wood [9] 36∆w Wood [29]
	path-width p	p	Dujmović et al. [6]
	band-width b track-number t 2-trees	⌈ b 2 ⌉ t -1 3	Heath and Rosenberg [19] Dujmović et al. [6] Rengarajan and Veni Madhavan [25] ‡
	k-ary butterfly d-ary de Bruijn	⌊ k 2 ⌋+1 d	Hasunuma [14] Hasunuma [14]
	Halin	3	Ganley [13]
	X-trees	2	Heath and Rosenberg [19]
	outerplanar	2	Heath et al. [15]
	arched levelled planar	1	Heath et al. [15]
	trees	1	Heath and Rosenberg [19]

  1 , x 2 , . . . , x d ) and (y 1 , y 2 , . . . , y d ) are in V s , and both (x 1 , x 2 , . . . , x d-1 + 1, x d ) and (y 1 , y 2 , . . . , y d-1 , y d + 1) are in V s+1 . Case 1. (x 1 , x 2 , . . . , x d ) ≺ (y 1 , y 2 , . . . , y d ): Let j be the first dimension for which x j < y j . If j ≤ d -2 then (x 1 , x 2 , . . . , x d-2 , x d-1 + 1, x d ) ≺ (y 1 , y 2 , . . . , y d-1 , y d + 1) , which implies that e and f are not nested. Observe that j = d as (x 1 , x 2 , . . . , x d ) and (y 1 , y 2 , . . . , y d ) differ in at least two coordinates, since i

  1 , y 2 , . . . , y d-1 , y d + 1) ≺ (x 1 , x 2 , . . . , x d-2 , x d-1 + 1, x d ), which implies that y d-1 ≤ x d-1 + 1. By Equation (5),x d-1 = y d-1 -1. Since x d-1 + x d = y d-1 + y d , we have x d = y d + 1, which implies that (y 1 , y 2 , . . . , y d-1 , y d + 1) = (x 1 , x 2 , . . . , x d-2 , x d-1 + 1, x d ) .That is, the right-hand endpoints of e and f are the same vertex. Hence e and f are not nested.Case 2. (y 1 , y 2 , . . . , y d ) ≺ (x 1 , x 2 , . . . , x d ): By the same argument employed above, the first coordinate for which (y 1 , y 2 , . . . , y d ) and (x 1 , x 2 , . . . , x d ) differ is d -1. That is, Since e and f are nested, we have (x 1 , x 2 , . . . , x d-2 , x d-1 + 1, x d ) ≺ (y 1 , y 2 , . . . , y d-1 , y d + 1). Thus x d-1 + 1 < y d-1 , which contradicts Equation[START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF]. Hence e and f are not nested.ThereforeQ 1 , Q 2 , . . . , Q d-2 , Q d-1 ∪ Q d isthe desired (d -1)-queue layout. ✷ More generally we have the following.

	y d-1 < x d-1 .			(6)
	Theorem 4 The queue-number of a generalised d-dimensional grid G = P k n1	P k n2	• • •	P k n

d

(where n i ≥ k + 1) satisfies:

Acknowledgements

Many thanks to Toru Hasunuma for invaluable comments on a preliminary draft of this paper. Thanks to the anonymous reviewers and the editor, Therese Biedl, for helpful suggestions.

† Supported by the Government of Spain grant MEC SB2003-0270, and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224. 1365-8050

sqn(G i ) .

✷

Grids

A d-dimensional grid is a graph P n1 P n2

Lemma 9 generalises as follows.