Familjerna EPT (s.k. EPG) Kantintersektion Diagram över stigar i ett träd (sp. i ett rutnät) är väl studerade grafklasser. Nyligen introducerade vi grafklasserna Edge-Intersecting och Non-Splitting Paths i ett träd (ENPT) och i ett rutnät (ENPG). Det visade sig att ENPG innehåller en oändlig hierarki av underklasser som erhålls genom att begränsa antalet kurvor på vägarna. Motiverad av detta resultat fokuserar vi i detta arbete på en böjning av ENPG-diagram. Vi visar att en böjning ENPG grafer är korrekt ingår i två böj ENPG grafer. Vi visar också att träd och cykler är en böjning ENPG grafer, och karakteriserar de delade grafer och co-bipartite grafer som är en böj ENPG. Vi bevisar att igenkänningsproblemet för en böj split grafer ENPG är NP-fullständig även i en mycket begränsad delfamilj av split grafer. Sist vi ger en linjär tidsigenkänning algoritm för en böj ENPG co-bipartite grafer.
I REF fokuserar vi på grafer med böj nummer 1.
Graphs of Edge-Intersecting and Non-Splitting One Bend Paths in a Grid
{'venue': 'Discrete Mathematics&Theoretical Computer Science, Vol. 19 no. 1, Graph Theory (June 12, 2017) dmtcs:3708', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}