Abstrakt. Traditionella representationer av grafer och deras dualer tyder på att de dubbla hörnen bör placeras inuti deras motsvarande primal ansikten, och kanterna på den dubbla grafen bör endast korsa deras motsvarande primal kanter. Vi anser att problemet med att samtidigt inbädda en planar graf och dess dubbla på ett litet heltal rutnät så att kanterna ritas som raka-linje segment och de enda korsningar är mellan primal-dual par av kanter. Vi tillhandahåller en O(n) tid algoritm som samtidigt inbäddar en 3-ansluten planar graf och dess dubbla på en (2n − 2) × (2n − 2) heltal rutnät, där n är det totala antalet hörn i grafen och dess dubbla. Alla kanter är dragna som raka segment utom en kant på yttersidan, som dras med hjälp av två segment.
Erten och Kobourov REF, presenterade en O(n) tid algoritm som resulterar i en samtidig ritning men tyvärr inte en RAC ritning av en treansluten planar graf och dess dubbla på en O(n 2 ) rutnät, där n är antalet hörn av G och G *.
Simultaneous Embedding of a Planar Graph and Its Dual on the Grid
{'venue': 'Theory of Computing Systems', 'journal': 'Theory of Computing Systems', 'mag_field_of_study': ['Computer Science', 'Mathematics']}