Are these inclusions between graph classes correct? for ISGCI

Question

Here are some inclusions between graph classes that I suspect to hold. In order to include them in ISGCI, they need a (reference to a) nice proof.

outerplanar << EPT

P_4-comparability << co-C_6-free

unipolar << biclique separable

unipolar << interval filament

perfectly orderable << co-sun-free

bip* << (anti-hole,odd-hole)-free

And a question: Is the book thickness of 2-subdivision unbounded?

Answer 1

Replaced earlier answer, which used an incorrect definition of interval filament graphs.

Unipolar graphs are interval filaments graphs. Brief sketch: If $G$ is unipolar there are vertex sets $A$ and $B$ s.th. $A$ induces a clique and $B$ induces a set of cliques with vertex sets $B_1, \ldots, B_k$, say.

Each filament has two endpoints on the x-axis, and we order the endpoints along the $x$-axis as $A, B_1, B^R_1, B_2, B^R_2, \ldots, B_k, B^R_k, A^R$, where we think of $A$, and $B_i$ as ordered sets, and let $X^R$ denote the reverse of the ordered set $X$.

We can then draw all filaments simultaneously as $/\backslash$-shaped curves and so that no two of the filaments intersect. To create an intersection between an $A$-filament $a$ and a $B_i$-filament $b$, let $x$ be a coordinate inside the group $B_i$, where both $a$ and $b$ are present. We can then push $a$ up (close to $x$) until it is above all the other $B_i$-filaments at $x$, and push $a$ down, until it it below all the other $A$-filaments at $x$, and then make $a$ and $b$ intersect. Creating intersections between two filaments belonging to the same group is similar (and easier).

Answer 2

outerplanar << EPT

We can prove it inductively for an outerplanar graph $G$.

If $G$ is disconnected then let $(T_1,{\cal P}_1)$ be an EPT representation of a component and let $(T_2,{\cal P}_2)$ be an EPT representation of the rest of the graph. Add an edge from $T_1$ to $T_2$ and to get a tree and take the union of the two sets of paths; this suffices.

If $v$ is a cut-vertex of $G$, let $G_1,G_2$ be subgraphs of $G$ with intersection $v$ and union $G$. By induction, let $(T_1,{\cal P}_1)$, $(T_2,{\cal P}_2)$ be EPT representations of $G_1,G_2$; let $P_1\in {\cal P}_1$ and $P_2\in {\cal P}_2$ represent $v$. Let $u_1,u_2$ be an endpoint of $P_1,P_2$, respectively. Take the union of $T_1$ and $T_2$ where we identify $u_1$ and $u_2$ and let ${\cal P}'$ be the union of ${\cal P}_1$ and ${\cal P}_2$ except that we replace $P_1$ and $P_2$ by their union, which is a path since they overlap at $u$. This suffices.

If $|V(G)|\le 2$, it's easy.

Otherwise $G$ is a 2-connected (WLOG embedded) outerplane graph. We show by induction that it has an EPT representation $(T, {\cal P})$ such that for each boundary edge $uv$, the paths representing $u$ and $v$ share an endpoint that is a leaf in $T$:

If $G$ is a $k$-cycle, it can be represented by a star $T$ with edges $e_1,\ldots,e_k=e_0$ with and paths which each contain two consecutive edges $e_{i-1},e_i$.

Otherwise it has a non-trivial weak dual; let $C$ be the cycle bounding a face that corresponds to a leaf in the weak dual. $C$ contains adjacent vertices $u,v$ such that $G' := G-(V(C)-\{u,v\})$ is a 2-connected outerplane graph, which, by induction, has an EPT representation $(T, {\cal P})$ such that for each boundary edge $uv$, the paths representing $u$ and $v$ share an endpoint $x$ that is a leaf in $T$. Let $x_0$ be the neighbor of $x$ in $T$ and let $k=|C|$. Add $k-1$ leaves $x_1,\ldots,x_{k-1}$ adjacent to $x$ in $T$ and add paths $x_{i-1}xx_i$ for $i=1,\ldots,k$ (where $x_k=x_0$) to $\cal P$ to get an EPT representation of $G$.