Disproving a conjecture on planar visibility graphs (Q5941094)

Two vertices \(A\) and \(B\) of a simple polygon \(P\) are (mutually) visible if \(\overline {AB}\) does not intersect the exterior of \(P.\) A graph \(G\) is a visibility graph if there exists a simple polygon \(P\) such that each vertex of \(G\) corresponds to a vertex of \(P\) and two vertices of \(G\) are joined by an edge if and only if their corresponding vertices in \(P\) are visible. No characterization of visibility graphs is available. Abello, Lin and Pisupati conjectured that every hamiltonian maximal planar graph with a 3-clique ordering is a visibility graph. In this paper, we disprove this conjecture.