Abstrakt. Fáry's teorem anger att varje plan graf kan ritas som en rät linje teckning. En plan graf är en graf inbäddad i ett plan utan kantkorsningar. I den här tidningen utvidgar vi Fárys teorem till icke-planära grafer. Mer specifikt studerar vi problemet med att rita 1-plansgrafer med raka kanter. En 1-plansgraf är en graf inbäddad i ett plan med högst en korsning per kant. Vi ger en karakterisering av de 1-plansgrafer som medger en rät linjedragning. Beviset för karakteriseringen består av en linjär tidstestande algoritm och en ritningsalgoritm. Vi visar också att det finns 1-plansgrafer för vilka varje straight-line-ritning har exponentiellt område. Så vitt vi vet är detta det första resultatet att utvidga Fárys teorem till icke-planära grafer.
Hong m.fl. REF gav en linjär tidstestnings- och ritningsalgoritm för att konstruera en rät linje 1-plansritning, om sådan finns.
Fáry’s Theorem for 1-Planar Graphs
{'venue': 'COCOON', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}