Warunki, aby wykres dwudzielny był płaski, bez krawędzi biegnących wokół wierzchołków

Dwustronny wykres jest płaski, jeśli nie ma nieletnich lub .$K_{3, 3}$$K_5$

Szukam koniecznych i / lub wystarczających warunków, aby umożliwić rysunki planarne bez krawędzi „przechodzących” przez zestawy wierzchołków. Są to rysunki spełniające:

1. Wszystkie wierzchołki jednej części są rysowane na jednej linii pionowej. Wierzchołki drugiej części są rysowane na równoległej linii pionowej.
2. Krawędzie nie przecinają się z wyjątkiem wierzchołków.
3. Krawędzie znajdują się na nieskończonym pasku między dwiema pionowymi liniami w punkcie 1.

Na przykład wszystkie rysunki tutaj oprócz prawego dolnego rogu nie są przykładami. Lewy dolny wykres można ponownie narysować, aby spełnić warunki, zamieniając pozycje Q i R. Górnych dwóch wykresów nie można przerysować, aby spełnić warunki.

Dwa górne wykresy to jedyne przeszkody, jakie mogłem znaleźć. Moje pytania to:

1. Czy ten problem ma nazwę?
2. Jakieś inne przeszkody, za którymi tęskniłem?
3. Wszelkie wskazówki, w jaki sposób mogę udowodnić, że te dwie przeszkody (wraz ze wszystkim, czego mi brakowało), oczywiście jako nieletni, są konieczne i wystarczające.

Zauważ, że to nie jest to samo, co bycie zewnętrznym, jest obrysem zewnętrznym (może być narysowany jako kwadrat), ale nie można go narysować, aby spełnić warunki, o których wspomniałem powyżej.$K_{2, 2}$

Twoje wykresy są dokładnie wykresami szerokości ścieżki  lub równoważnie lasów, z których każdy jest gąsienicą . Gąsienice mają dwie istotne cechy:$1$

• są to drzewa, w których istnieje jedna ścieżka zawierająca każdy wierzchołek stopnia większy niż  ;$1$

• są to drzewa, w których każdy wierzchołek ma co najwyżej dwóch sąsiadów niebędących liśćmi.

Lemat 1. Każda gąsienica jest w twojej klasie.

Dowód. Niech będzie gąsienicą, a będzie najdłuższą ścieżką zawierającą każdy wierzchołek stopnia  lub więcej. Zauważ, że maksymalnie . Możemy stworzyć rysunek  , najpierw rysując  jako zygzak, a następnie dodając wierzchołki stopnia- przylegające do  między a  . $G$$P=x_1\dots x_\ell$$2$$d(x_1)=d(x_\ell)=1$$G$$P$$1$$x_i$$x_{i-1}$$x_{i+1}$$\Box$

Lemat 2. Każdy wykres w twojej klasie jest acykliczny.$G$

Dowód. Załóżmy, że zawiera cykl i załóżmy, że ma rysunek wymaganej formy. Wlog,  jest powyżej  . Ale wtedy musimy mieć powyżej  ponieważ w przeciwnym razie linie i  przecinałyby się. Przez indukcję  jest powyżej  dla wszystkich i podobnie dla  . Ale potem dowolna linia$G$$x_1y_1x_2y_2\dots x_ky_kx_1$$x_2$$x_1$$y_2$$y_1$$x_1y_1$$x_2y_2$$x_{i+1}$$x_i$$i\in\{1, \dots, k-1\}$$y$$y_kx_1$musi albo opuścić obszar między dwiema kolumnami wierzchołków lub przekroczyć każdą drugą krawędź w cyklu. Jest to sprzeczne z naszym założeniem, że wykres ma prawidłowy rysunek. $\Box$

Lemat 3. Każda nie związana gąsienica nie jest w twojej klasie.

Dowód. Niech będzie połączonym wykresem, który nie jest gąsienicą. Jeśli zawiera cykl, nie ma go w klasie według Lemat  , więc możemy założyć, że jest to drzewo. Jeśli nie jest to gąsienica, musi zawierać wierzchołek  z wyraźnymi sąsiadami , i  , z których każdy ma stopień co najmniej   .$G$$2$$x$$y_1$$y_2$$y_3$$2$

Załóżmy, że mamy rysunek  o wymaganych właściwościach. Wlog,  jest powyżej  a  jest powyżej  . Niech będzie sąsiadem  . Krawędź  musi przekroczyć lub  , co jest sprzeczne z naszym założeniem, że wykres zawiera rysunek wymaganej formy. $G$$y_2$$y_1$$y_3$$y_2$$z\neq x$$y_2$$y_2z$$xy_1$$xy_3$$\Box$

Twierdzenie. Twoja klasa grafów jest dokładnie klasą lasów, z których każdy jest gąsienicą.

Dowód. Niech będzie wykresem. Oczywiście,  jest w twojej klasie, jeśli i tylko wtedy, gdy każdy komponent jest: jeśli żaden komponent nie może być narysowany zgodnie z wymaganiami, cały wykres nie może; jeśli każdy element można narysować zgodnie z wymaganiami, wówczas można narysować cały wykres, ustawiając elementy jeden nad drugim. Wynik następuje teraz w Lematach i  . $G$$G$$1$$3$$\Box$

Następstwo. Twoja klasa grafów jest klasą grafów, które nie mają lub poddziału  jako drobne.$K_3$$K_{1,3}$

Dowód. Są to przeszkody dla ścieżki o szerokości $1$ . $\Box$

Są to w zasadzie przeszkody, które znalazłeś: potrzebujesz zamiast ponieważ ten ostatni dopuszczałby do klasy; podział jest dokładnie twoją drugą przeszkodą.$K_3$$K_4$$K_3$$K_{1,3}$

Tak więc wymyśliłem następującą odpowiedź:

Jak już wspomniano, istnieją tylko dwa możliwe przypadki, których nie można zmienić.

Drugi przypadek ma prawidłowa reprezentacja jeśli przyjmiemy graf dwudzielny, ponieważ Wikipedia definiuje Graf dwudzielny jak: każda krawędź łączy wierzchołek w jednego w .$U$$V$

Edycja: Źle odczytałem wykres, przepraszam za to.

Pozostaje nam to tylko z , co jest warunkiem, którego chcesz uniknąć. Odwrotnie, wystarczającym warunkiem jest to, że twój dwudzielny wykres nie ma w sobie pełnego podgrafu.$K_{2,2}$

Aby udowodnić, że jakikolwiek inny podgraf jest prawidłowy, możesz wyobrazić sobie następujące rzeczy:

Po pierwsze, zakładamy, że nie mamy krawędzi i zaczynamy od dowolnej krawędzi . Dodając kolejną krawędź, mamy trzy możliwe przypadki:$e$

Pierwszy przypadek polega na tym, że mamy węzeł, który nie zaczyna się ani nie kończy na tym samym węźle co pierwsza krawędź. To pozostawia nam bez problemu i możemy kontynuować wstawianie.

Drugi przypadek polega na tym, że mamy krawędź, która po drodze przecina inną, już istniejącą, krawędź. W takim przypadku musimy zamienić wierzchołek lub (ten z już istniejącą krawędzią) na jedną z nowych krawędzi lub , tak abyśmy nadal spełniali kryteria.$V_1$$V_2$$V_3$$V_4$

Zakłada się, że nie mamy żadnych dalszych krawędzi rozpoczynających się i kończących w węzłach do zamiany, co prowadzi nas do następującego trzeciego przypadku: Po zamianie jednego z czterech wierzchołków musimy prześledzić wszystkie inne połączenia z zamienionego wierzchołka.$V1-V4$

Znów możemy znaleźć tylko trzy rozwiązania: albo prześledzimy końcowe połączenie, albo powtórzymy krok, który już zrobiliśmy wcześniej (śledząc wszystkie pozostałe kroki). Jeśli skończymy na końcowym węźle, możemy zamienić wszystkie śledzone węzły.

Ostatni możliwy przypadek doprowadzi do węzła, który już odwiedziliśmy, co dałoby nam pełny podgraph, który możemy następnie zredukować do wspomnianego warunku .$K_{2,2}$

EDYCJA: Aby rozszerzyć ten dowód na drugi przypadek, musimy spojrzeć na następujące warunki:

Ogólnie rzecz biorąc, jeśli mamy podsgraf z co najmniej jednym hubem (3 lub więcej połączeń), jest to „dość łatwe”.

Nie możemy zmienić kolejności, jeśli mamy wyświetlaną wielkość liter z więcej niż dwoma sąsiadami wyższego stopnia niż jeden ( ). Jest to ważne, ponieważ zapewnia wiedzę o dalszych sąsiadach. Nie musimy nawet śledzić ich dalej, aby uniknąć kręgów (jak w pierwszym przypadku), ale wystarczy sprawdzić bezpośrednich sąsiadów.$\langle k\rangle > 1$

Ponieważ sam mam tylko niewielką wiedzę w tej dziedzinie, ale nadal chcę zapewnić możliwe rozwiązanie, podłączyłem do ciebie jeden (mam nadzieję) odpowiedni artykuł

Jeśli ktoś nazwałby ten problem, chciałbym się tego nauczyć, zwłaszcza, że ​​wymyśliłem to rozwiązanie jedynie w oparciu o przemyślenia z twierdzenia Fáry'ego i kompletne dwustronne podrozdziały.