Naslov
Graph colouring and its application within cartography

Autori
Glaurdić, Mate ; Beban-Brkić, Jelka

Vrsta, podvrsta i kategorija rada
Sažeci sa skupova, sažetak, stručni

Izvornik
Book of abstracts of the 19th Scientific- Professional Colloquium on Geometry and Graphics, Starigrad Paklenica, September 4-8, 2016 / Došlić, Tomislav ; Jurkin, Ema - Zagreb : Hrvatsko društvo za geometriju i grafiku, 2016, 23-23

Skup
19th Scientific-Professional Colloquium on Geometry and Graphics

Mjesto i datum
Starigrad, Hrvatska, 04.09.2016. - 08.09.2016

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
graph ; graph colouring ; map ; map colouring ; 4 colour theorem

Sažetak
The problem of colouring geographical political maps has historically been associated with the theory of graph colouring. In the middle of the 19th century the following question was posed: how many colours are needed to colour a map in a way that countries sharing a border are coloured differently. The solution has been reached by linking maps and graphs. It took more than a century to prove that 4 colours are sufficient to create a map in which neighbouring countries have different colours. In graph theory, graph colouring is a special case of graph labelling. It is about assigning a colour to graph elements: vertices, edges, regions, with certain restrictions. With this presentation we would like to assess the elements of the theory of graph colouring with an emphasis on its application on practical problems in the field of surveying namely cartography. A mathematical basis for administrative map colouring will be given along with the chronology of proving The 4 Colour Theorem. In addition, World maps and map of Croatia will be shown, to determine the minimum number of colours needed to colour a map properly in practice. Application Cartography is a discipline that deals with collecting, processing, storing and usage of spatial information, being especially concerned in their visualisation i.e. cartographic representation. A map is a connected planar graph where all vertices have a degree of at least 3. It is a unit consisting of interconnected regions/countries. The border of each region represents a closed curve that can be divided into as many parts/edges as the region has neighbours. The two countries that share a common edge are considered adjacent. As well as being a tool that is used for better orientation in space and for travel from point A to point B, maps also possess an artistic component. Each colour causes a certain stimulus therefore it is necessary to pay special attention to the choice of colours and their diversity when producing a map. Selecting the optimal number of colours is also valuable because it enables cheaper reproduction of maps.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Geodezija

POVEZANOST RADA