Универсальное множество точек

Нерешённые проблемы математики: Размер универсальных множеств точек планарных графов подквадратичен?

Универсальное множество точек порядка n — это множество S точек евклидовой плоскости со свойством, что любой планарный граф с n вершинами имеет рисунок с прямыми рёбрами, в котором все вершины располагаются в точках множества S.

Границы размеров универсального множества точек

Рисунок графа вложенных треугольников на решётке. В любом рисунке этого графа по меньшей мере половина треугольников должна иметь образовывать вложенную цепочку, так что потребуется ограничивающий прямоугольник размером по меньшей мере n/3 × n/3. Показанное на рисунке представление графа имеет близкое к этому значение n/3 × n/2

Если n не превосходит десяти, существует универсальное множество точек, имеющее в точности n точек, но для всех n ≥ 15 требуются дополнительные точки [1].

Некоторые авторы показали, что подмножество целочисленной решётки размера O(n) × O(n) является универсальным. В частности, Фрейсикс, Пах и Поллак[2] показали, что решётка (2n − 3) × (n − 1) является универсальной, а Шнайдер[3] уменьшил до треугольного подмножества решётки (n − 1) × (n − 1) с n2/2 − O(n) точками. Модифицируя метод Фрейсикса, Паха и Шнайдера, Бранденбург[4] нашёл вложение любого планарного графа в треугольное подмножество решётки, содержащей 4n2/9 точек. Универсальное множество точек в виде прямоугольной решётки должно иметь размер по меньшей мере n/3 × n/3 [5], но это не исключает возможность существования меньшего универсального множества точек других типов. Наименьшие известные универсальные множества точек не основаны на решётках, а строятся из суперсхем[англ.] (перестановок, содержащих все образы перестановок[англ.] заданного размера). Универсальные множества точек, построенные таким образом, имеют размер n2/4 − O(n)[6].

Фрейсикс, Пах и Поллак[2] доказали первую нетривиальную нижнюю границу размера универсального множества точек в виде n + Ω(√n), а Хробак и Карлофф[7] показали, что универсальное множество точек должно содержать по меньшей мере 1.098n − o(n) точек. Куровски[8] предложил даже более сильную границу 1.235n − o(n), которая остаётся лучшей нижней границей [9].

Закрытие промежутка между известными линейными границами и квадратичными верхними границами остаётся открытой проблемой[10].

Специальные классы графов

Подклассы планарных графов могут, в общем случае, иметь меньшие универсальные множества (множества точек, которые позволяют рисование всех графов с n вершинами с прямыми рёбрами в подклассе), чем полный класс всех планарных графов, и во многих случаях существуют универсальные множества точек, имеющие в точности n точек. Например, несложно видеть, что любое множество из n точек в выпуклой позиции[англ.] (которые служат вершинами выпуклого многоугольника), является универсальным для n вершинных внешнепланарных графов, и, в частности, для деревьев. Менее очевидно, что любое множество из n точек в общем положении (никакие три не лежат на одной прямой) остаётся универсальным для внешнепланарных графов[11].

Планарные графы, которые могут быть разбиты на вложенные циклы, и планарные графы с ограниченной путевой шириной имеют универсальное множество точек почти линейного размера[12][6]. Планарные 3-деревья имеют универсальные множества точек размера O(n5/3). Та же самая граница имеет место для параллельно-последовательных графов[13].

Другие стили рисования

Дугова диаграмма

Как и в случае рисования графов с прямыми рёбрами, универсальные множества точек изучались для других стилей. В большинстве этих случаев существуют универсальные множества точек, имеющие в точности n точек, и основываются они на топологическом книжном вложении, в котором вершины располагаются на прямой на плоскости, а рёбра рисуются как кривые, которые пересекают эту линию максимум один раз. Например, любое множество n коллинеарных точек является универсальным для дуговой диаграммы, в которой каждое ребро представлено либо как одна полуокружность, либо как гладкая кривая, образованная двумя полуокружностями[14].

Можно показать, что при использовании подобного расположения любая выпуклая кривая на плоскости содержит подмножество из n точек, которое является универсальным для рисунков в виде ломаных с максимум одним изломом на ребро[15]. Это множество содержит только вершины рисунка, но не точки излома. Известны бо́льшие множества, которые можно использовать для рисунков с помощью ломаных, в которых вершины и все точки излома являются точками множества[16].

Примечания

  1. ↑ Cardinal, Hoffmann, Kusters, 2015.
  2. ↑ 1 2 de Fraysseix, Pach, Pollack, 1988.
  3. ↑ Schnyder, 1990.
  4. ↑ Brandenburg, 2008.
  5. ↑ Dolev, Leighton, Trickey, 1984; Chrobak, Karloff, 1989; Demaine, O'Rourke, 2002–2012. Более слабую квадратичную границу на размер решётки, требуемой для рисунки планарного графа, дал до этого Валиант Valiant (1981).
  6. ↑ 1 2 Bannister, Cheng, Devanny, Eppstein, 2013.
  7. ↑ Chrobak, Karloff, 1989.
  8. ↑ Kurowski, 2004.
  9. ↑ Мондал (Mondal 2012) утверждал, что доказательство Куровски ошибочно, но позднее (после дискуссии с Джином Кардиналом) отозвал своё утверждение. См. Объяснение доказательства Куровски Архивная копия от 15 марта 2017 на Wayback Machine.
  10. ↑ Demaine, O'Rourke, 2002–2012; Brandenburg, Eppstein, Goodrich, Kobourov, 2003; Mohar, 2007.
  11. ↑ Gritzmann, Mohar, Pach, Pollack, 1991.
  12. ↑ Angelini, Di Battista, Kaufmann, Mchedlidze, 2012.
  13. ↑ Fulek, Toth, 2013.
  14. ↑ Giordano, Liotta, Mchedlidze, Symvonis, 2007.
  15. ↑ Everett, Lazard, Liotta, Wismath, 2010.
  16. ↑ Dujmović, Evans, Lazard, Lenhart, 2013.

Литература

  • Patrizio Angelini, Giuseppe Di Battista, Michael Kaufmann, Tamara Mchedlidze, Vincenzo Roselli, Claudio Squarcella. Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21–23, 2011, Revised Selected Papers / Marc van Kreveld, Bettina Speckmann. — Berlin, Heidelberg: Springer-Verlag, 2012. — Т. 7034. — С. 75–85. — (LNCS). — doi:10.1007/978-3-642-25878-7_8.
  • Michael J. Bannister, Zhanpeng Cheng, William E. Devanny, David Eppstein. Proc. 21st International Symposium on Graph Drawing (GD 2013). — 2013.
  • Franz J. Brandenburg. The International Conference on Topological and Geometric Graph Theory. — Elsevier, 2008. — Т. 31. — С. 37–40. — (Electronic Notes in Discrete Mathematics). — doi:10.1016/j.endm.2008.06.005.
  • Franz-Josef Brandenburg, David Eppstein, Michael T. Goodrich, Stephen G. Kobourov, Giuseppe Liotta, Petra Mutzel. Graph Drawing: 11th International Symposium, GD 2003, Perugia, Italy, September 21–24, 2003 Revised Papers / Giuseppe Liotta. — Springer-Verlag, 2003. — Т. 2912. — С. 515–539. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-24595-7_55.. См., в частности задачу 11 на стр. 520.
  • Jean Cardinal, Michael Hoffmann, Vincent Kusters. On universal point sets for planar graphs // Journal of Graph Algorithms and Applications. — 2015. — Т. 19. — С. 529–547. — doi:10.7155/jgaa.00374.
  • M. Chrobak, H. Karloff. A lower bound on the size of universal sets for planar graphs // SIGACT News. — 1989. — Т. 20. — С. 83–86. — doi:10.1145/74074.74088.
  • Hubert de Fraysseix, János Pach, Richard Pollack. Twentieth Annual ACM Symposium on Theory of Computing. — 1988. — С. 426–433. — ISBN 0-89791-264-0. — doi:10.1145/62212.62254.
  • E. Demaine, J. O'Rourke. The Open Problems Project. — 2002–2012.
  • Danny Dolev, Tom Leighton, Howard Trickey. Planar embedding of planar graphs // Advances in Computing Research. — 1984. — Т. 2. — С. 147–161.
  • V. Dujmović, W. S. Evans, S. Lazard, W. Lenhart, G. Liotta, D. Rappaport, S. K. Wismath. On point-sets that support planar graphs // Comput. Geom. Theory Appl.. — 2013. — Т. 46, вып. 1. — С. 29–50.
  • Hazel Everett, Sylvain Lazard, Giuseppe Liotta, Stephen Wismath. Universal Sets of n Points for One-Bend Drawings of Planar Graphs with n Vertices // Discrete and Computational Geometry. — 2010. — Т. 43, вып. 2. — С. 272–288. — doi:10.1007/s00454-009-9149-3.
  • Radoslav Fulek, Csaba Toth. Algorithms & Data Structures Symposium (WADS). — 2013.
  • Francesco Giordano, Giuseppe Liotta, Tamara Mchedlidze, Antonios Symvonis. Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings. — Springer, 2007. — Т. 4835. — С. 172–183. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-77120-3_17.
  • P. Gritzmann, B. Mohar, János Pach, Richard Pollack. Embedding a planar triangulation with vertices at specified positions // American Mathematical Monthly. — 1991. — Т. 98, вып. 2. — С. 165–166.
  • Maciej Kurowski. A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs // Information Processing Letters. — 2004. — Т. 92, вып. 2. — С. 95–98. — doi:10.1016/j.ipl.2004.06.009.
  • Bojan Mohar. Open Problem Garden. — 2007.
  • Debajyoti Mondal. Embedding a Planar Graph on a Given Point Set. — Department of Computer Science, University of Manitoba, 2012. — (Masters thesis).
  • Walter Schnyder. Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA). — 1990. — С. 138–148.
  • L. G. Valiant. Universality considerations in VLSI circuits // IEEE Transactions on Computers. — 1981. — Т. C-30, вып. 2. — С. 135–140. — doi:10.1109/TC.1981.6312176.

Read other articles:

Polina Tsurskaya

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Desember 2023. Polina TsurskayaTsurskaya pada tahun 2015Informasi PribadiNama lengkapPolina Igorevna TsurskayaMewakili negara RusiaLahir11 Juli 2001 (umur 22)Omsk, RusiaTempat tinggalMoscow, RusiaTinggi171 cm (5 ft 7+1⁄2 in)Mantan pelatihEl...

 

Mass

Amount of matter present in an object This article is about the scientific concept. For the main liturgical service in some Christian churches, see Mass (liturgy). For other uses, see Mass (disambiguation). MassA 2 kg (4.4 lb) cast iron weight used for balancesCommon symbolsmSI unitkilogramExtensive?yesConserved?yes Part of a series onClassical mechanics F = d d t ( m v ) {\displaystyle {\textbf {F}}={\frac {d}{dt}}(m{\textbf {v}})} Second law of motion History Timeline Textboo...

 

The Farm (Canada)

Official residence in Quebec, CanadaThe FarmLa Ferme (French)The Farm in autumn 2007General informationTypeOfficial residenceTown or cityKingsmere, QuebecCountryCanadaCoordinates45°29′6″N 75°50′28″W / 45.48500°N 75.84111°W / 45.48500; -75.84111Current tenantsGreg Fergus, Speaker of the House of CommonsOwnerThe King in Right of CanadaLandlordNational Capital CommissionTechnical detailsFloor area5,000 square feet (460 m2)Grounds1.74 hectares (4.3 acres)...

Thomas Jex-Blake

Anglican priest and educationalist Thomas Jex-Blake (John Everett Millais, 1875) Thomas William Jex-Blake (1832–1915) was an Anglican priest and educationalist.[1][2] He was born on 26 January 1832, the son of lawyer Thomas Jex-Blake and the brother of Sophia Jex-Blake, who was a pioneer in women doctors in the United Kingdom.[3] He was educated at Rugby[4] and University College, Oxford.[5] His career in education began with a school master position ...

 

Benghazi

This article is about the city. For the 1942 Italian film, see Bengasi (film). For the 1955 American film, see Bengazi (film). For the 2012 attack on U.S. diplomats, see 2012 Benghazi attack. It has been suggested that this article should be split into a new article titled Benghazi District. (discuss) (December 2023) This article needs to be updated. Please help update this article to reflect recent events or newly available information. (October 2015) City in Cyrenaica, LibyaBenghazi بنغ�...

 

Anna Jean Ayres

Anna Jean AyresLahir(1920-01-18)18 Januari 1920Visalia, CaliforniaMeninggal16 Desember 1989(1989-12-16) (umur 69)Los AngelesDikenal atasPsikolog perkembanganKarya terkenalIntegrasi Sensorik dan Gangguan Belajar (1972) Anna Jean Ayres (18 Januari 1920 – 16 Desember 1989) adalah ahli terapi okupasi dari tahun 1946 - 1955 pada beberapa pusat rehabilitasi di California. Dia mengajar dan melakukan riset pada bagian terapi okupasi[1] di Universitas Southern California....

Pollinator-mediated selection

Process in which pollenators effects a plant's evolution Evolution of multiple pollination syndromes. The columns from left to right are examples of bee, hummingbird and moth-pollination syndromes. Each row shows representatives of the same genus. The top row are columbines (Ranunculaceae). The second row are beardtongues (Plantagineaceae). Third row are catchfly (Caryophylaceae). The fourth row are morning glories (Convolvulaceae). The fifth row are larkspurs (Ranunculaceae) and the last row...

 

Demographics of Liberia

Demographics of LiberiaPopulation pyramid of Liberia in 2020Population5,358,483 (2022 est.)Growth rate2.73% (2022 est.)Birth rate36.64 births/1,000 population (2022 est.)Death rate6.62 deaths/1,000 population (2022 est.)Net migration rate-2.74 migrant(s)/1,000 population (2022 est.)Age structure0–14 years43.35%65 and over2.83%NationalityNationalityLiberianLanguageOfficialEnglishRepublic of Liberia History Politics Demographics Culture Geography Music Communications Transport Economy Armed ...

 

Несторианство

ХристианствоБиблия Ветхий Завет Новый Завет Евангелие Десять заповедей Нагорная проповедь Апокрифы Бог, Троица Бог Отец Иисус Христос Святой Дух История христианства Апостолы Хронология христианства Раннее христианство Гностическое христианство Вселенские соборы Н...

Biawu, Kota Selatan, Gorontalo

BiawuKelurahanNegara IndonesiaProvinsiGorontaloKotaGorontaloKecamatanKota SelatanKode Kemendagri75.71.02.1012 Kode BPS7571020010 Luas... km²Jumlah penduduk... jiwaKepadatan... jiwa/km² Kantor Lurah Biawu Biawu adalah salah satu kelurahan di wilayah kecamatan Kota Selatan, Kota Gorontalo, Provinsi Gorontalo, Indonesia. Pranala luar (Indonesia) Keputusan Menteri Dalam Negeri Nomor 050-145 Tahun 2022 tentang Pemberian dan Pemutakhiran Kode, Data Wilayah Administrasi Pemerintahan, dan Pula...

 

Maeun-tang

Korean spicy fish soup This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Maeun-tang – news · newspapers · books · scholar · JSTOR (February 2013) (Learn how and when to remove this message) Maeun-tangAlternative namesSpicy fish stewTypeTangPlace of originKoreaMain ingredientsFishIngredients generally used...

 

尼古拉·雷日科夫

尼古拉·雷日科夫Николай Рыжков攝於2019年 俄羅斯聯邦委員會议员任期2003年9月17日—2023年9月25日选区别尔哥罗德州 俄羅斯国家杜马议员任期1995年12月17日—2003年9月17日选区别尔哥罗德州 苏联部長會議主席任期1985年9月27日—1991年1月14日总统米哈伊尔·谢尔盖耶维奇·戈尔巴乔夫前任尼古拉·亚历山德罗维奇·吉洪诺夫继任瓦连京·谢尔盖耶维奇·帕夫洛夫（总�...

土库曼斯坦总统

土库曼斯坦总统土库曼斯坦国徽土库曼斯坦总统旗現任谢尔达尔·别尔德穆哈梅多夫自2022年3月19日官邸阿什哈巴德总统府（Oguzkhan Presidential Palace）機關所在地阿什哈巴德任命者直接选举任期7年，可连选连任首任萨帕尔穆拉特·尼亚佐夫设立1991年10月27日 土库曼斯坦土库曼斯坦政府与政治 国家政府 土库曼斯坦宪法 国旗 国徽 国歌 立法機關（英语：National Council of Turkmenistan） ...

 

Marc Andreessen

Marc AndreessenMarc Andreessen en 2013.FonctionMembre du conseil d'administrationMetadepuis juin 2008BiographieNaissance 9 juillet 1971 (52 ans)Cedar FallsNationalité américaineDomiciles New Lisbon, AthertonFormation Université de l'Illinois à Urbana-Champaign (licence (en)) (jusqu'en 1993)New Lisbon High School (en)Activités Informaticien, programmeur, ingénieur logiciel, investisseur, blogueur, entrepreneur, inventeur, ingénieurConjoint Laura Arrillaga-Andreessen (en) (depuis 20...

 

Universitas Pasundan

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Universitas Pasundan – berita · surat kabar · buku · cendekiawan · JSTOR Universitas Pasundanᮅᮔᮤᮑᮨᮁᮞᮤᮒᮞ᮪ ᮕᮞᮥᮔ᮪ᮓᮔ᮪Pilihan Pasti Setiap GenerasiNama lainUNPAS (Pasunda...

Northern Isles

Pair of archipelagos near Scotland This article is about the large group of Scottish islands including Orkney and Shetland. For the northern islands of Shetland, see North Isles. Northern IslesLocationNorthern IslesNorthern Isles shown within ScotlandOS grid referenceHY99Coordinates59°50′N 2°00′W / 59.833°N 2.000°W / 59.833; -2.000Physical geographyIsland groupBritish IslesArea2,464 km2[1]Highest elevationWard Hill 481 m (1,578 ft)AdministrationSov...

 

Isoetes

Genus of vascular plants in the family Isoetaceae IsoetesTemporal range: Jurassic–Recent PreꞒ Ꞓ O S D C P T J K Pg N Isoetes tegetiformans with U.S. penny for scale Scientific classification Kingdom: Plantae Clade: Tracheophytes Clade: Lycophytes Class: Lycopodiopsida Order: Isoetales Family: Isoetaceae Genus: IsoetesL. Species See text Isoetes, commonly known as the quillworts, is a genus of lycopod. It is the only living genus in the family Isoetaceae and order Isoetales. There are c...

 

Brunei

Country in Southeast Asia State of BruneiNegara Brunei Darussalam (Malay) Flag Emblem Motto: الدائمون المحسنون بالهدى‎Ad-dāʾimūna al-muḥsinūna bi-l-hudā(Sentiasa membuat kebajikan dengan petunjuk Allah)Always in service with God's guidanceAnthem: Allah Peliharakan Sultanﷲ ڤليهاراکن سلطان‎God Bless the SultanShow globeShow map of south-east AsiaLocation of Brunei (green)in the ASEAN (dark grey)  –...

Tsai Ing-wen

President of Taiwan from 2016 to 2024 For the Taiwanese political scientist with the same name, see Tsai Ying-wen (political scientist).In this Taiwanese name, the surname is Tsai. Tsai Ing-wen蔡英文Official portrait, 20167th President of the Republic of ChinaIn office20 May 2016 – 20 May 2024Premier See list Lin ChuanLai Ching-teSu Tseng-changChen Chien-jen Vice PresidentChen Chien-jenLai Ching-tePreceded byMa Ying-jeouSucceeded byLai Ching-te13th, 15th and 17th Chairwoman of t...

 

Proliga 2017

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Diskusi terkait dapat dibaca pada Pembicaraan:Proliga 2017. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Proliga 2017 – berita · surat kabar · buku · cendekiawan · JSTOR Proliga 2017FederasiPersatuan Bola Voli Seluruh IndonesiaLigaProligaOlahragaBo...