In short, a combinatorial map is a graph along with a counterclockwise order of incident half-edges ("darts") at each vertex. This is exactly enough data to record the topological information about how a given connected planar graph is embedded in the plane. They also work for graphs in general oriented surfaces, with the proviso that the complement of the graph consists of a bunch of faces homeomorphic to disks. For example, no annulus faces.
When reading the article, it seemed like what the author was doing was to construct something like a combinatorial map from the purported intersections then use that to answer inside/outside questions. (A graph by itself is unable to answer these questions since it's merely abstract vertices and edges. While the code they use shows the use of graphs, the graphs contain the geometric information of the vertex locations, which sort of lets you work with it as if it were a combinatorial map.)