Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface

• Název česky: Aproximace průsečíkového čísla grafů nakreslitelných na orientovaných plochách
• Autoři: HLINĚNÝ Petr; CHIMANI Markus
• Rok publikování: 2010
• Druh: Článek ve sborníku
• Konference: ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)
• Fakulta / Pracoviště MU: Fakulta informatiky

www

• conference
• Proceedings address

• Obor: Informatika
• Klíčová slova: crossing number; crossing minimization; surface
• Popis: Podáme $O(n\log n)$ algoritmus s konstantním aproximačním faktorem pro průsečíkové číslo grafu G omezeného stupně, který má husté nakreslení na libovolném fixním orientovaném povrchu.

Související projekty

• Institut Teoretické Informatiky
• Vysoce paralelní a distribuované výpočetní systémy
• Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti