Abstrakt. Vi etablerar en en-till-en korrespondens mellan 1-plans grafer och allmänna och hålfria 4-kartor grafer och visar att 1-plans grafer kan kännas igen i polynom tid om de korsas-augmented, helt triangulated, respektive maximal 1-planar, med ett polynom av grad 120, 3, respektive 5.
I dokumentet REF diskuterades ett samband mellan kartgrafer och 1-plansgrafer, ett intressant ämne i grafritning.
On 4-Map Graphs and 1-Planar Graphs and their Recognition Problem
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}