3
$\begingroup$

The well-known max cut problem asks for a largest cut of a graph $G$. A cut of maximal size clearly corresponds to a bipartite subgraph of maximal size. After my inquiry, in planar graphs, the maximum-cut problem is dual to the route inspection problem (the problem of finding a shortest tour that visits each edge of a graph at least once)

I would like to ask if there is some theoretical research on the maximum cut of the planar graph, such as finding some upper or lower bounds. Or for some special planar graphs such as triangulation graphs, is there a corresponding study?

Thank you very much for any advice.

Improve this question
$\endgroup$
3
  • $\begingroup$ A cut in a triangulation can't use all three edges of a face, so an upper bound is two edges from each face. This is achieved by triangulations whose dual is hamiltonian. $\endgroup$
    – Brendan McKay
    Commented Mar 4, 2022 at 6:59
  • $\begingroup$ Thanks, Sir. I noticed that there was some discussion about the lower bounds of the maximum cut for some graphs. [AS B B, SCOTT A D. Better Bounds for Max Cut[J]] ., but I didn't see anything talk about planar graph. $\endgroup$
    – Licheng Zhang
    Commented Mar 4, 2022 at 9:50
  • 1
    $\begingroup$ The following post on mathSE addresses the lower bound: math.stackexchange.com/questions/1918960/…. This lower bound is tight and is obtained by maximal planar graphs. $\endgroup$
    – Pranay Gorantla
    Commented Jan 24, 2023 at 20:43

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .